Elias Koutsoupias
Professor of Computer Science
University of Athens
Panepistimiopolis, Ilissia
Athens 15784

phone: +30 210 7275122
fax: +30 210 7275114

E. Koutsoupias and C. Papadimitriou. On the k-server conjecture. Journal of the ACM, 42(5):971--983, September 1995.
Download: pdf ps


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.


@string{jacm= {Journal of the ACM}}

  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}}

  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},