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. The 2-evader problem. Information Processing Letters 57(5):249--252, March 1996.
Download: pdf ps


It is shown that the work function algorithm for the 2-evader problem has competitive ratio m-2 for all metric spaces with m points. This settles the k-server conjecture for metric spaces with k+2 points.


@string{ipl= {Information Processing Letters}}

  author =       {E. Koutsoupias  and  C. Papadimitriou},
  title =        {The 2-evader problem},
  journal =      ipl,
  volume =       57,
  number =       5,
  pages =        {249--252},
  month =        mar,
  year =         1996