𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Competitive k-server algorithms

✍ Scribed by Amos Fiat; Yuval Rabani; Yiftach Ravid

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
1008 KB
Volume
48
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we give deterministic competitive k-server algorithms for all k and all metric spaces. This settles the k-server conjecture 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 we can prove is exponential in the number of servers. Thus, the question of the minimal competitive ratio for arbitrary metric spaces is still open.

πŸ“œ SIMILAR VOLUMES

A competitive 2-server algorithm
A competitive 2-server algorithm
✍ Sandy Irani; Ronitt Rubinfeld πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 842 KB
The Distributedk-Server Problemβ€”A Compet
The Distributedk-Server Problemβ€”A Competitive Distributed Translator fork-Server Algorithms
✍ Yair Bartal; Adi RosΓ©n πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 243 KB

Algorithms Ž . x 11 1990 , 208᎐230 in a distributed setting. Given a network of n processors and k identical mobile servers, requests for service appear at the processors and a server must reach the request point. In addition to modeling problems in computer networks where k identical mobile resour

Generosity Helps or an 11-Competitive Al
Generosity Helps or an 11-Competitive Algorithm for Three Servers
✍ M. Chrobak; L.L. Larmore πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 1010 KB

We propose a new algorithm, called Equipoise, for the \(k\)-server problem, and we prove that it is two-competitive for two servers and 11 -competitive for three servers. For \(k=3\), this is a substantial improvement over previously known constants. The algorithm uses several general techniques-con

Geometric two-server algorithms
Geometric two-server algorithms
✍ Ran El-Yaniv; Jon Kleinberg πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 406 KB
Competitive paging algorithms
Competitive paging algorithms
✍ Amos Fiat; Richard M Karp; Michael Luby; Lyle A McGeoch; Daniel D Sleator; Neal πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 949 KB