Artículo

Feuerstein, E.; Lucchesi C.L.; Moura A.V. "Uniform service systems with k servers" (1998) 3rd Latin American Symposium on Theoretical Informatics, LATIN 1998 . 1380:23-32
El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte la política de Acceso Abierto del editor

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. © Springer-Verlag Berlin Heidelberg 1998.

Registro:

Documento: Artículo
Título:Uniform service systems with k servers
Autor:Feuerstein, E.; Lucchesi C.L.; Moura A.V.
Filiación:Depto. De Computación FCEyN, Universidad de Buenos Aires Instituto de Ciencias, Universidad de General Sarmiento, Argentina
Palabras clave:Set theory; Topology; Competitive ratio; K-server; Lower and upper bounds; Metric spaces; On-line algorithms; Service systems; Total distances; Uniform metric; Information science
Año:1998
Volumen:1380
Página de inicio:23
Página de fin:32
Título revista:3rd Latin American Symposium on Theoretical Informatics, LATIN 1998
Título revista abreviado:Lect. Notes Comput. Sci.
ISSN:03029743
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v1380_n_p23_Feuerstein

Referencias:

  • Alborzi, H., Torng, E., Uthaisombut, P., Wagner, S., The k-client problem (1995) Proc. Of Eigth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
  • Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L., Talamo, M., Competitive algorithms for the traveling salesman (1995) Proc. Of Workshop on Algorithms and Data Structures (WADS'95), , Springer-Verlag
  • Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L., Talamo, M., Serving requests with on-line routing (1995) Proc. Of 4Th Scandinavian Workshop on Algorithm Theory (SWAT'94), pp. 37-48. , Springer-Verlag, July
  • Ben-David, S., Borodin, A., Karp, R., Tardos, G., Widgerson, A., On the power of randomization in on-line algorithms (1994) Algorithmica, 11, pp. 2-14
  • Borodin, A., Irani, S., Raghavan, P., Schieber, B., Competitive paging with locality of reference (1991) Proc. Of 23Rd ACM Symposium on Theory of Computing, pp. 249-259
  • Borodin, A., Linial, N., Saks, M., An optimal online algorithm for metrical task system (1992) Journal of the Association for Computing Machinery, 39 (4), pp. 745-763
  • Chrobak, M., Larmore, L., The server problem and on-line games (1992) On-Line Algorithms, pp. 11-64. , AMS-ACM
  • Feuerstein, E., Paging more than one page (1995) Proceedings of the Second Latin American Symposium on Theoretical Informatics (LATIN95), pp. 272-287. , Springer-Verlag, An improved version of this paper will appear in Theoretical Computer Science (1997)
  • Feuerstein, E., Strejilevich De Loma, A., On multi-threaded paging (1996) Proceedings of the 7Th International Symposium on Algorithms and Computation (ISAAC'96), , Springer-Verlag
  • Garey, M.R., Johnson, D.S., (1979) Computers and Intractabiliy - a Guide to the Theory of Np-Completeness, , W.H. Freeman and Company, San Francisco
  • Karlin, A., Manasse, M., Rudolph, L., Sleator, D., Competitive snoopy caching (1988) Algorithmica, 30, pp. 79-119
  • Manasse, M.S., McGeoch, L.A., Sleator, D.D., Competitive algorithms for server problems (1990) Journal of Algorithms, 11 (2), pp. 208-230
  • Motwani, R., Lecture Notes on Approximation Algorithms, , Technical Report, Stanford University
  • Raghavan, P., Snir, M., (1990) Memory versus Randomization in On-Line Algorithms, , RC 15622, IBM
  • Sleator, D.D., Tarjan, R.E., Amortized efficiency of list update and paging rules (1985) Communications of ACM, 28 (2), pp. 202-208A4 -

Citas:

---------- APA ----------
Feuerstein, E., Lucchesi C.L. & Moura A.V. (1998) . Uniform service systems with k servers. 3rd Latin American Symposium on Theoretical Informatics, LATIN 1998 , 1380, 23-32.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v1380_n_p23_Feuerstein [ ]
---------- CHICAGO ----------
Feuerstein, E., Lucchesi C.L., Moura A.V. "Uniform service systems with k servers" . 3rd Latin American Symposium on Theoretical Informatics, LATIN 1998 1380 (1998) : 23-32.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v1380_n_p23_Feuerstein [ ]
---------- MLA ----------
Feuerstein, E., Lucchesi C.L., Moura A.V. "Uniform service systems with k servers" . 3rd Latin American Symposium on Theoretical Informatics, LATIN 1998 , vol. 1380, 1998, pp. 23-32.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v1380_n_p23_Feuerstein [ ]
---------- VANCOUVER ----------
Feuerstein, E., Lucchesi C.L., Moura A.V. Uniform service systems with k servers. Lect. Notes Comput. Sci. 1998;1380:23-32.
Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v1380_n_p23_Feuerstein [ ]