E. Koutsoupias and C. Papadimitriou.
On the k-server conjecture.
Journal of the ACM, 42(5):971--983, September 1995.
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.Bib
@string{jacm= {Journal of the ACM}}
@Article{KP95,
author = {E. Koutsoupias and C. Papadimitriou},
title = {On the {$k$}-Server Conjecture},
journal = jacm,
year = 1995,
month = sep,
volume = 42,
number = 5,
pages = {971--983}
}
@string{STOC94 = {Proceedings of the Twenty-Sixth Annual ACM Symposium
on the Theory of Computing}}
@InProceedings{KP94a,
author = {E. Koutsoupias and C. Papadimitriou},
title = {On the {$k$}-server conjecture},
booktitle = STOC94,
year = 1994,
month = {23--25 } # may,
pages = {507--511},
address = {Montreal, Quebec, Canada},
}