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
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 [ ]
