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

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

E. Koutsoupias. Weak adversaries for the k-server problem. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, New York City, NY, pages 444--449, 17--19 October 1999.
Download: pdf ps


We study the k-server problem when the off-line algorithm has fewer than k servers. We give two upper bounds of the cost wfa(rho) of the Work Function Algorithm. The first upper bound is k*opt_h(rho)+(h-1)*opt_k(rho)$, where opt_m(rho) denotes the optimal cost to service rho by m servers. The second upper bound is 2*h*opt_h(rho)-opt_k(rho) for h<=k. Both bounds imply that the Work Function Algorithm is (2k-1)-competitive. Perhaps more important is our technique which seems promising for settling the k-server conjecture. The proofs are simple and intuitive and they do not involve potential functions. We also apply the technique to give a simple condition for the Work Function Algorithm to be k-competitive; this condition results in a new proof that the k-server conjecture holds for k=2.


@string{FOCS99 = {Proceedings of the 40th Annual Symposium on Foundations of
                  Computer Science}}

  author =       {E. Koutsoupias},
  title =        {Weak adversaries for the $k$-server problem},
  booktitle =    FOCS99,
  year =         1999,
  month =        {17--19 } # oct,
  pages =        {444--449},
  address =      {New York City, NY},