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

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.

See also

Competitive Ratio, Dynamic Programming, k-Server Problem, Online Algorithm

Explore with Wolfram|Alpha

References

Coester, C.; Koutsoupias, E.; and Zbysiński, M. "The -Server Conjecture Is True." 14 Sep 2026. https://arxiv.org/abs/2609.15979.Koutsoupias, E. and Papadimitriou, C. H. "On the -Server Conjecture." J. ACM 42, 971-983, 1995. https://doi.org/10.1145/210118.210128.

Cite this as:

Weisstein, Eric W. "Work Function Algorithm." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/WorkFunctionAlgorithm.html

Subject classifications