The 3-server problem in the plane

In the k-server problem we wish to minimize, in an online fashion, the movement cost of k servers in response to a sequence of requests (we assume that k⩾2). The request issued at each step is specified by a point r in a given metric space M. To serve this request, one of the k servers must move to r. It is known that if M has at least k+1 points then no online algorithm for the k-server problem in M has competitive ratio smaller than k. The best known upper bound on the competitive ratio in arbitrary metric spaces, by Koutsoupias and Papadimitriou (J. ACM 42 (1995) 971), is 2k−1. There are only a few special cases for which k-competitive algorithms are known: for k=2, when M is a tree, or when M has at most k+2 points. We prove that the Work Function Algorithm is 3-competitive for the 3-server problem in the Manhattan plane. As a corollary, we obtain a 4. 243-competitive algorithm for 3 servers in the Euclidean plane. The best previously known competitive ratio for 3 servers in these metric spaces was 5.

Authors

• Wolfgang W. Bein
• Marek Chrobak
• Lawrence L. Larmore

Keywords

No keywords are indexed for this paper.