Back to results

Institutes outside Greece

On-Line Algorithms and the k-Server Conjecture

Abstract

dc:description

The Work Function Algorithm, a natural algorithm for the ^-server problem, is shown to have competitive ratio at most 2k —1 for all metric spaces. It is also shown that the ^-server conjecture, which states that there is an on-line algorithm for the /^-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. viii

Degree

thesis:*
Grantor dc:publisher
Institutes outside Greece
Year dc:date
1994

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Koutsoupias, Elias
  • Κουτσουπιάς, Ηλίας

Subjects

dc:subject × 2

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/10816

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Koutsoupias, Elias; Κουτσουπιάς, Ηλίας. On-Line Algorithms and the k-Server Conjecture. Institutes outside Greece, 1994. http://hdl.handle.net/10442/hedi/10816