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

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

Elias Koutsoupias: The k-server problem. Computer Science Review 3(2): 105-118 (2009).
Download: pdf ps


The k-server problem is perhaps the most influential online problem: natural, crisp, with a surprising technical depth that manifests the richness of competitive analysis. The k-server conjecture, which was posed more than two decades ago when the problem was first studied within the competitive analysis framework, is still open and has been a major driving force for the development of the area online algorithms. This article surveys some major results for the k-server problem.


  author    = {Elias Koutsoupias},
  title     = {The k-server problem},
  journal   = {Computer Science Review},
  volume    = {3},
  number    = {2},
  year      = {2009},
  pages     = {105-118},
  ee        = {http://dx.doi.org/10.1016/j.cosrev.2009.04.002},