Uniform service systems with k servers
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 travel...
| Autor principal: | |
|---|---|
| Otros Autores: | , |
| Formato: | Acta de conferencia Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
Springer Verlag
1998
|
| Acceso en línea: | Registro en Scopus Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 05225caa a22006017a 4500 | ||
|---|---|---|---|
| 001 | PAPER-12418 | ||
| 003 | AR-BaUEN | ||
| 005 | 20240513200907.0 | ||
| 008 | 190411s1998 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-84949237332 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Feuerstein, E. | |
| 245 | 1 | 0 | |a Uniform service systems with k servers |
| 260 | |b Springer Verlag |c 1998 | ||
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Alborzi, H., Torng, E., Uthaisombut, P., Wagner, S., The k-client problem (1995) Proc. Of Eigth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Chrobak, M., Larmore, L., The server problem and on-line games (1992) On-Line Algorithms, pp. 11-64. , AMS-ACM | ||
| 504 | |a 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) | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Karlin, A., Manasse, M., Rudolph, L., Sleator, D., Competitive snoopy caching (1988) Algorithmica, 30, pp. 79-119 | ||
| 504 | |a Manasse, M.S., McGeoch, L.A., Sleator, D.D., Competitive algorithms for server problems (1990) Journal of Algorithms, 11 (2), pp. 208-230 | ||
| 504 | |a Motwani, R., Lecture Notes on Approximation Algorithms, , Technical Report, Stanford University | ||
| 504 | |a Raghavan, P., Snir, M., (1990) Memory versus Randomization in On-Line Algorithms, , RC 15622, IBM | ||
| 504 | |a Sleator, D.D., Tarjan, R.E., Amortized efficiency of list update and paging rules (1985) Communications of ACM, 28 (2), pp. 202-208A4 - | ||
| 520 | 3 | |a 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. |l eng | |
| 593 | |a Depto. De Computación FCEyN, Universidad de Buenos Aires Instituto de Ciencias, Universidad de General Sarmiento, Argentina | ||
| 690 | 1 | 0 | |a SET THEORY |
| 690 | 1 | 0 | |a TOPOLOGY |
| 690 | 1 | 0 | |a COMPETITIVE RATIO |
| 690 | 1 | 0 | |a K-SERVER |
| 690 | 1 | 0 | |a LOWER AND UPPER BOUNDS |
| 690 | 1 | 0 | |a METRIC SPACES |
| 690 | 1 | 0 | |a ON-LINE ALGORITHMS |
| 690 | 1 | 0 | |a SERVICE SYSTEMS |
| 690 | 1 | 0 | |a TOTAL DISTANCES |
| 690 | 1 | 0 | |a UNIFORM METRIC |
| 690 | 1 | 0 | |a INFORMATION SCIENCE |
| 700 | 1 | |a Lucchesi, C.L. | |
| 700 | 1 | |a Moura, A.V. | |
| 711 | 2 | |d 20 April 1998 through 24 April 1998 |g Código de la conferencia: 147019 | |
| 773 | 0 | |d Springer Verlag, 1998 |g v. 1380 |h pp. 23-32 |p Lect. Notes Comput. Sci. |n Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |x 03029743 |w (AR-BaUEN)CENRE-983 |z 3540642757 |z 9783540642756 |t 3rd Latin American Symposium on Theoretical Informatics, LATIN 1998 | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-84949237332&partnerID=40&md5=a792f9827d7016663c04444867e0a8df |x registro |y Registro en Scopus |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_03029743_v1380_n_p23_Feuerstein |x handle |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v1380_n_p23_Feuerstein |x registro |y Registro en la Biblioteca Digital |
| 961 | |a paper_03029743_v1380_n_p23_Feuerstein |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 963 | |a VARI | ||