Abstract
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. 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. (We assume that k ≥ 2.) 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 [6], is 2k-1. There is only a number of 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.
The main result of this paper is that theWork 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 spaces was 5.
Research supported by NSF grant CCR-9503441.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Marek Chrobak, Howard Karloff, Tom H. Payne, and Sundar Vishwanathan. New results on server problems. SIAM Journal on Discrete Mathematics, 4:172–181, 1991.
Marek Chrobak and Lawrence L. Larmore. An optimal online algorithm for k servers on trees. SIAM Journal on Computing, 20:144–148, 1991.
Marek Chrobak and Lawrence L. Larmore. The server problem and on-line games. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 7, pages 11–64, 1992.
Marek Chrobak and Lawrence L. Larmore. Metrical task systems, the server problem, and the work function algorithm. In Online Algorithms: State of the Art, pages 74–94. Springer-Verlag, 1998.
Elias Koutsoupias and Christos Papadimitriou. On the k-server conjecture. In Proc. 26th Symp. Theory of Computing, pages 507–511, 1994.
Elias Koutsoupias and Christos Papadimitriou. On the k-server conjecture. Journal of the ACM, 42:971–983, 1995.
Elias Koutsoupias and Christos Papadimitriou. The 2-evader problem. Information Processing Letters, 57:249–252, 1996.
Mark Manasse, Lyle A. McGeoch, and Daniel Sleator. Competitive algorithms for server problems. Journal of Algorithms, 11:208–230, 1990.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bein, W.W., Chrobak, M., Larmore, L.L. (1999). The 3-Server Problem in the Plane. In: Nešetřil, J. (eds) Algorithms - ESA’ 99. ESA 1999. Lecture Notes in Computer Science, vol 1643. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48481-7_27
Download citation
DOI: https://doi.org/10.1007/3-540-48481-7_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66251-8
Online ISBN: 978-3-540-48481-3
eBook Packages: Springer Book Archive