The work function algorithm is an online algorithm that chooses its next state using the optimal offline costs for the input revealed
so far. In the k-server problem, let 
be the minimum cost of serving
the first 
requests from a specified initial configuration and then ending with the servers
at configuration 
.
This function is the work function. It can be updated
from 
by dynamic programming.
The distance between configurations 
and 
is the minimum total distance
required to move the servers from one configuration to the other,
 |
where 
is the underlying metric and 
is the symmetric group
of permutations of the 
servers. If the current configuration is 
and the next request is 
, the work function algorithm chooses
![C_t in argmin_(X:r_t in X)[w_t(X)+D(C_(t-1),X)].](/images/equations/WorkFunctionAlgorithm/NumberedEquation2.svg) |
Thus the chosen configuration must contain the requested point, and ties may be broken arbitrarily. Configurations are multisets of server locations, so multiple servers may occupy the same point.
Koutsoupias and Papadimitriou (1995) proved a competitive ratio of at most 
for the k-server
problem. Coester et al. (2026) reported the optimal competitive
ratio 
,
with independent specialist verification and external peer review not reported as
of Sep. 18, 2026.
-Server
Conjecture Is True." 14 Sep 2026. 
-Server Conjecture." J. ACM 42, 971-983,
1995.