Abstract:

We prove that the work function algorithm for the k-server problem has competitive ratio at most 2k-1. Manasse, McGeoch, and Sleator conjectured that the competitive ratio for the k-server problem is exactly k (it is trivially at least k); previously the best known upper bound was exponential in k. Our proof involves three crucial ingredients: A quasiconvexity property of work functions, a duality lemma that uses quasiconvexity to characterize the configurations that achieve maximum increase of the work function, and a potential function that exploits the duality lemma.

Postscript

Pdf

BibTeX