up E. Koutsoupias and C. Papadimitriou. The 2-evader problem. Information Processing Letters 57(5):249--252, March 1996.

Abstract:

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.

 Postscript    Pdf    BibTeX  
 


Elias Koutsoupias / elias_at_di.uoa.gr