GENEROSITY HELPS OR AN 11-COMPETITIVE ALGORITHM FOR 3 SERVERS

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.