up E. Koutsoupias. On-line algorithms and the k-server conjecture. PhD thesis, University of California, San Diego, La Jolla, California, June 1994.


The Work Function Algorithm, a natural algorithm for the k-server problem, is shown to have competitive ratio at most 2k-1 for all metric spaces.It is also shown that the k-server conjecture, which states that there is an on-line algorithm for the k-server problem with competitive ratio k, holds for all metric spaces with k+2 points. Furthermore, two refinements of competitive analysis are proposed and studied: diffuse adversaries and comparative analysis.They address successfully some of the drawbacks of competitive analysis.

 Postscript    Pdf    BibTeX  

Fri Jul 2 14:54:54 2004
Elias Koutsoupias / elias:@:di.uoa.gr