Bio and Coordinates

Publications

Talks

Courses

For Students

Elias
Elias Koutsoupias
Professor of Computer Science
University of Athens
Panepistimiopolis, Ilissia
Athens 15784
Greece

phone: +30 210 7275122
fax: +30 210 7275114

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

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.

Bib 

@PhdThesis{Kou94,
  author =       {E. Koutsoupias},
  title =        {On-line algorithms and the $k$-server conjecture},
  school =       {University of California, San Diego},
  year =         1994,
  month =        jun,
  address =      {La Jolla, California}
}