Skip to main content
SpringerLink
Log in

Uniform service systems with k servers

  • Conference paper
  • First Online:
LATIN'98: Theoretical Informatics (LATIN 1998)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1380))

Included in the following conference series:

Abstract

We consider the problem of k servers situated on a uniform metric space that must serve a sequence of requests, where each request consists of a set of locations of the metric space and can be served by moving a server to any of the nodes of the set. The goal is to minimize the total distance traveled by the servers. This problem generalizes a problem presented by Chrobak and Larmore in [7]. We give lower and upper bounds on the competitive ratio achievable by on-line algorithms for this problem, and consider also interesting particular cases.

This work was partially supported by the KIT program of the European Community (Project DYNDATA), by University of Buenos Aires' Programación para Investigadores Jóvenes, project EX070/J “Algoritmos Eficientes para Problemas On-line con Aplicaciones” and by UBACYT project “Modelos y Técnicas de Optimizatión Combinatoria”.

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.

References

  1. H. Alborzi, E. Torng, P. Uthaisombut, and S. Wagner. The k-client problem. In Proc. of Eigth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1995.

    Google Scholar 

  2. G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie, and M. Talamo. Competitive algorithms for the traveling salesman. In Proc. of Workshop on Algorithms and Data Structures (WADS'95), Springer-Verlag, 1995.

    Google Scholar 

  3. G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie, and M. Talamo. Serving requests with on-line routing. In Proc. of 4th Scandinavian Workshop on Algorithm Theory (SWAT'94), pages 37–48, Springer-Verlag, July 1995.

    Google Scholar 

  4. S. Ben-David, A. Borodin, R. Karp, G. Tardos, and A. Widgerson. On the power of randomization in on-line algorithms. Algorithmica, 11:2–14, 1994.

    Article  MathSciNet  Google Scholar 

  5. A. Borodin, Sandy Irani, P. Raghavan, and B. Schieber. Competitive paging with locality of reference. In Proc. of 23rd ACM Symposium on Theory of Computing, pages 249–259, 1991.

    Google Scholar 

  6. A. Borodin, N. Linial, and M. Saks. An optimal online algorithm for metrical task system. Journal of the Association for Computing Machinery, 39(4):745–763, 1992.

    MathSciNet  Google Scholar 

  7. M. Chrobak and L. Larmore. The server problem and on-line games. In On-line Algorithms, pages 11–64, AMS-ACM, 1992.

    Google Scholar 

  8. E. Feuerstein. Paging more than one page. In Proceedings of the Second Latin American Symposium on Theoretical Informatics (LATIN95), pages 272–287, Springer-Verlag, 1995. An improved version of this paper will appeax in Theoretical Computer Science (1997).

    Google Scholar 

  9. E. Feuerstein and A. Strejilevich de Loma. On multi-threaded paging. In Proceedings of the 7th International Symposium on Algorithms and Computation (ISAAC'96), Springer-Verlag, 1996.

    Google Scholar 

  10. M. R. Garey and D. S. Johnson. Computers and Intractabiliy — A Guide to the Theory of NP-completeness. W.H. Freeman and Company, San Francisco, 1979.

    Google Scholar 

  11. A. Karlin, M. Manasse, L. Rudolph, and D. Sleator. Competitive snoopy caching. Algorithmica, 3():79–119, 1988.

    Article  MathSciNet  Google Scholar 

  12. M.S. Manasse, L.A. McGeoch, and D.D. Sleator. Competitive algorithms for server problems. Journal of Algorithms, 11(2):208–230, 1990.

    Article  MathSciNet  Google Scholar 

  13. R. Motwani. Lecture Notes on Approximation Algorithms. Technical Report, Stanford University.

    Google Scholar 

  14. P. Raghavan and M. Snir. Memory versus randomization in on-line algorithms. RC 15622, IBM, 1990.

    Google Scholar 

  15. D.D. Sleator and R.E. Tarjan. Amortized efficiency of list update and paging rules. Communications of ACM, 28(2):202–208, 1985.

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dpto. de Computatión, FCEyN, Universidad de Buenos Aires Institute de Ciencias, Argentina

    Esteban Feuerstein

  2. Universidad de General Sarmiento, Argentina

    Esteban Feuerstein

Authors
  1. Esteban Feuerstein
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Cláudio L. Lucchesi Arnaldo V. Moura

Rights and permissions

Reprints and permissions

Copyright information

© 1998 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Feuerstein, E. (1998). Uniform service systems with k servers. In: Lucchesi, C.L., Moura, A.V. (eds) LATIN'98: Theoretical Informatics. LATIN 1998. Lecture Notes in Computer Science, vol 1380. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054307

Download citation

  • DOI: https://doi.org/10.1007/BFb0054307

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-64275-6

  • Online ISBN: 978-3-540-69715-2

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation