Competitive k-server algorithms
Authors:
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 454-463
Abstract
Deterministic competitive k-server algorithms are given for all k and all metric spaces. This settles the k-server conjecture of M.S. Manasse et al. (1988) up to the competitive ratio. The best previous result for general metric spaces was a three-server randomized competitive algorithm and a nonconstructive proof that a deterministic three-server competitive algorithm exists. The competitive ratio the present authors can prove is exponential in the number of servers. Thus, the question of the minimal competitive ratio for arbitrary metric spaces is still open. The methods set forth here also give competitive algorithms for a natural generalization of the k-server problem, called the k-taxicab problem.Keywords
This publication has 7 references indexed in Scilit:
- On the power of randomization in on-line algorithmsAlgorithmica, 1994
- An optimal on-line algorithm for metrical task systemJournal of the ACM, 1992
- A strongly competitive randomized paging algorithmAlgorithmica, 1991
- New Ressults on Server ProblemsSIAM Journal on Discrete Mathematics, 1991
- Random walks on weighted graphs, and applications to on-line algorithms1990
- Competitive snoopy cachingAlgorithmica, 1988
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985