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