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

Abstract:

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  
 


Elias Koutsoupias / elias_at_di.uoa.gr