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.
Fri Jul 2 14:54:54 2004 Elias Koutsoupias / elias:@:di.uoa.gr |