✦ LIBER ✦

Generosity Helps or an 11-Competitive Algorithm for Three Servers

✍ Scribed by M. Chrobak; L.L. Larmore

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 1010 KB
Volume: 16
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1994.1011

No coin nor oath required. For personal study only.

✦ Synopsis

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-convex hulls, work functions, and forgiveness. 1994 Academic Press. Inc.