On the k -server conjecture

Abstract

We prove that the work function algorithm for the k -server problem has a competitive ratio at most 2 k −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 exponential in k . Our proof involves three crucial ingredients: A quasiconvexity property of work functions, a duality lemma that uses quasiconvexity to characterize the configuration that achieve maximum increase of the work function, and a potential function that exploits the duality lemma.