COMPETITIVE KAPPA-SERVER ALGORITHMS

In this paper we give deterministic competitive k-server algorithms fo r 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 non- constructive proof that a deterministic three-server competitive algor ithm 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. (C) 1994 Academic Press, I nc.