ON THE K-SERVER CONJECTURE

We prove that the work function algorithm for the k-server problem has a competitive ratio at most 2k - 1. Manasse et al. [1988] 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 ex ponential in k. Our proof involves three crucial ingredients: A quasic onvexity property of work functions, a duality lemma that uses quasico nvexity to characterize the configuration that achieve maximum increas e of the work function, and a potential function that exploits the dua lity lemma.