Abstract
We prove that there exits a randomized online algorithm for the 2-server 3-point problem whose expected competitive ratio is at most 1.5897. This is the first nontrivial upper bound for randomized k-server algorithms in a general metric space whose competitive ratio is well below the corresponding deterministic lower bound (= 2 in the 2-server case).
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
Appel, K., Haken, W.: Every planar map is four colorable. Illinois Journal of Mathematics 21(5), 429–597 (1977)
Bartal, Y., Bollobas, B., Mendel, M.: A Ramsey-type theorem for metric spaces and its applications for metrical task systems and related problems. In: Proc. 42nd FOCS, pp. 396–405. IEEE, Los Alamitos (2001)
Bartal, Y., Chrobak, M., Larmore, L.L.: A randomized algorithm for two servers on the line. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol. 1461, pp. 247–258. Springer, Heidelberg (1998)
Bein, W., Iwama, K., Kawahara, J., Larmore, L.L., Oravec, J.A.: A randomized algorithm for two servers in cross polytope spaces. In: Kaklamanis, C., Skutella, M. (eds.) WAOA 2007. LNCS, vol. 4927, pp. 246–259. Springer, Heidelberg (2008)
Bein, W., Larmore, L.L., Noga, J.: Equitable revisited. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 419–426. Springer, Heidelberg (2007)
Bein, W., Chrobak, M., Larmore, L.L.: The 3-server problem in the plane. In: Nešetřil, J. (ed.) ESA 1999. LNCS, vol. 1643, pp. 301–312. Springer, Heidelberg (1999)
Chrobak, M., Karloff, H., Payne, T.H., Vishwanathan, S.: New results on server problems. SIAM J. Discrete Math. 4, 172–181 (1991)
Chrobak, M., Larmore, L.L.: An optimal online algorithm for k servers on trees. SIAM J. Comput. 20, 144–148 (1991)
Chrobak, M., Larmore, L.L.: The server problem and on-line games. In: McGeoch, L.A., Sleator, D.D. (eds.) On-line Algorithms. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 7, pp. 11–64. AMS/ACM (1992)
Chrobak, M., Larmore, L.L., Lund, C., Reingold, N.: A better lower bound on the competitive ratio of the randomized 2-server problem. Inform. Process. Lett. 63, 79–83 (1997)
Feige, U., Goemans, M.X.: Approximating the value of two prover proof systems, with applications to max-2sat and max-dicut. In: Proc. 3rd ISTCS, pp. 182–189 (1995)
Fiat, A., Karp, R., Luby, M., McGeoch, L.A., Sleator, D., Young, N.E.: Competitive paging algorithms. J. Algorithms 12, 685–699 (1991)
Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115–1145 (1995)
Horiyama, T., Iwama, K., Kawahara, J.: Finite-state online algorithms and their automated competitive analysis. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol. 4288, pp. 71–80. Springer, Heidelberg (2006)
Karlin, A.R., Kenyon, C., Randall, D.: Dynamic tcp acknowledgement and other stories about e/(e − 1). In: Proc. 33rd STOC, pp. 502–509. ACM, New York (2001)
Karloff, H., Zwick, U.: A 7/8-approximation algorithm for max 3sat. In: Proc. 38th FOCS, pp. 406–417. IEEE, Los Alamitos (1997)
Koutsoupias, E., Papadimitriou, C.: Beyond competitive analysis. In: Proc. 35th FOCS, pp. 394–400. IEEE, Los Alamitos (1994)
Koutsoupias, E., Papadimitriou, C.: On the k-server conjecture. J. ACM 42, 971–983 (1995)
Lund, C., Reingold, N.: Linear programs for randomized on-line algorithms. In: Proc. 5th SODA, pp. 382–391. ACM/SIAM (1994)
Manasse, M., McGeoch, L.A., Sleator, D.: Competitive algorithms for server problems. J. Algorithms 11, 208–230 (1990)
Reingold, N., Westbrook, J., Sleator, D.D.: Randomized competitive algorithms for the list update problem. Algorithmica 11, 15–32 (1994)
Seiden, S.S.: On the online bin packing problem. J. ACM 49(5), 640–671 (2002)
Trevisan, L., Sorkin, G.B., Sudan, M., Williamson, D.P.: Gadgets, approximation, and linear programming. SIAM J. Comput. 29(6), 2074–2097 (2000)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bein, W., Iwama, K., Kawahara, J. (2008). Randomized Competitive Analysis for Two-Server Problems. In: Halperin, D., Mehlhorn, K. (eds) Algorithms - ESA 2008. ESA 2008. Lecture Notes in Computer Science, vol 5193. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87744-8_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-87744-8_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87743-1
Online ISBN: 978-3-540-87744-8
eBook Packages: Computer ScienceComputer Science (R0)