Abstract
dc:descriptionThe 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 × 2Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/10816