A Randomized Algorithm for Two Servers in Cross Polytope Spaces | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Randomized Algorithm for Two Servers in Cross Polytope Spaces

  • Conference paper
Approximation and Online Algorithms (WAOA 2007)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4927))

Included in the following conference series:

  • 575 Accesses

Abstract

It has been a long-standing open problem to determine the exact randomized competitiveness of the 2-server problem, that is, the minimum competitiveness of any randomized online algorithm for the 2-server problem. For deterministic algorithms the best competitive ratio that can be obtained is 2 and no randomized algorithm is known that improves this ratio for general spaces. For the line, Bartal et al. [2] give a \(\frac{155}{78}\) competitive algorithm, but their algorithm is specific to the geometry of the line.

We consider here the 2-server problem over Cross Polytope Spaces M 2,4. We obtain an algorithm with competitive ratio of \(\frac{19}{12}\), and show that this ratio is best possible. This algorithm gives the second non-trivial example of metric spaces with better than 2 competitive ratio.

The algorithm uses a design technique called the knowledge state technique – a method not specific to M 2,4.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Achlioptas, D., Chrobak, M., Noga, J.: Competitive analysis of randomized paging algorithms. Theoret. Comput. Sci. 234, 203–218 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  2. 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)

    Chapter  Google Scholar 

  3. Bein, W., Larmore, L.L., Noga, J.: Equitable revisited. In: Proceedings of the 15th Annual European Symposium on Algorithms. LNCS, vol. 4698, pp. 419–426. Springer, Heidelberg (2007)

    Google Scholar 

  4. Bein, W., Larmore, L.L., Reischuk, R.: Knowledge states for the caching problem in shared memory multiprocessor systems. In: Proceedings of the 7th International Symposium on Parallel Architectures, Algorithms and Networks, pp. 307–312. IEEE, Los Alamitos (2004)

    Chapter  Google Scholar 

  5. Bein, W., Larmore, L.L., Reischuk, R.: Knowledge state algorithms: Randomization with limited information (2007), Arxiv: archive.org/cs/0701142

  6. Bein, W., Larmore, L.L., Reischuk, R.: Knowledge states: A tool for randomized online algorithms. In: Proceedings of the 41st Annual Hawaii International Conference on System Sciences (CD-ROM), p. 10. IEEE Computer Society Press, Los Alamitos (2008)

    Google Scholar 

  7. Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)

    MATH  Google Scholar 

  8. Chrobak, M., Karloff, H., Payne, T.H., Vishwanathan, S.: New results on server problems. SIAM J. Discrete Math. 4, 172–181 (1991)

    Article  MathSciNet  Google Scholar 

  9. Chrobak, M., Larmore, L.L.: An optimal online algorithm for k servers on trees. SIAM J. Comput. 20, 144–148 (1991)

    Article  MathSciNet  Google Scholar 

  10. 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)

    Article  MathSciNet  Google Scholar 

  11. Koutsoupias, E., Papadimitriou, C.: Beyond competitive analysis. In: Proc. 35th Symp. Foundations of Computer Science (FOCS), pp. 394–400. IEEE, Los Alamitos (1994)

    Chapter  Google Scholar 

  12. Koutsoupias, E., Papadimitriou, C.: On the k-server conjecture. J. ACM 42, 971–983 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  13. Lund, C., Reingold, N.: Linear programs for randomized on-line algorithms. In: Proc. 5th Symp. on Discrete Algorithms (SODA), pp. 382–391. ACM/SIAM (1994)

    Google Scholar 

  14. Manasse, M., McGeoch, L.A., Sleator, D.: Competitive algorithms for server problems. J. Algorithms 11, 208–230 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  15. Schläfli, L.: Theorie der vielfachen Kontinuität. Birkhäuser, Basel (1857)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Center for the Advanced Study of Algorithms, School of Computer Science, University of Nevada, Las Vegas, Nevada, 89154, USA

    Wolfgang Bein, Lawrence L. Larmore & James A. Oravec

  2. School of Informatics, Kyoto University, Kyoto, 606-8501, Japan

    Kazuo Iwama & Jun Kawahara

Authors
  1. Wolfgang Bein
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kazuo Iwama
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jun Kawahara
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Lawrence L. Larmore
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. James A. Oravec
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Christos Kaklamanis Martin Skutella

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bein, W., Iwama, K., Kawahara, J., Larmore, L.L., Oravec, J.A. (2008). A Randomized Algorithm for Two Servers in Cross Polytope Spaces. In: Kaklamanis, C., Skutella, M. (eds) Approximation and Online Algorithms. WAOA 2007. Lecture Notes in Computer Science, vol 4927. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77918-6_20

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-77918-6_20

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-77917-9

  • Online ISBN: 978-3-540-77918-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation