{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:22:16Z","timestamp":1725488536562},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671411"},{"type":"electronic","value":"9783540465416"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46541-3_49","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T12:03:24Z","timestamp":1186056204000},"page":"593-604","source":"Crossref","is-referenced-by-count":5,"title":["The Weighted 2-Server Problem"],"prefix":"10.1007","author":[{"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ji\u0159\u00ed","family":"Sgall","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,3,24]]},"reference":[{"key":"49_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1007\/3-540-61680-2_72","volume-title":"Proc. 4th European Symp. on Algorithms","author":"D. Achlioptas","year":"1996","unstructured":"D. Achlioptas, M. Chrobak, and J. Noga. Competitive analysis of randomized paging algorithms. In Proc. 4th European Symp. on Algorithms, volume 1136 of Lecture Notes in Computer Science, pages 419\u2013430. Springer, 1996."},{"key":"49_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1007\/3-540-19487-8_20","volume-title":"Proc. 1st Scandinavian Workshop on Algorithm Theory","author":"R. A. Baeza-Yates","year":"1988","unstructured":"R. A. Baeza-Yates, J. C. Culberson, and G. J. E. Rawlins. Searching with uncertainty. In Proc. 1st Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, pages 176\u2013189. Springer, 1988."},{"key":"49_CR3","doi-asserted-by":"crossref","unstructured":"Y. Bartal, A. Blum, C. Burch, and A. Tomkins. A polylog(n)-competitive algorithm for metrical task systems. In Proc. 29th Symp. Theory of Computing, pages 711\u2013719, 1997.","DOI":"10.1145\/258533.258667"},{"key":"49_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/3-540-68530-8_21","volume-title":"Proc. 6th European Symp. on Algorithms","author":"Y. Bartal","year":"1998","unstructured":"Y. Bartal, M. Chrobak, and L. L. Larmore. A randomized algorithm for two servers on the line. In Proc. 6th European Symp. on Algorithms, Lecture Notes in Computer Science, pages 247\u2013258. Springer, 1998."},{"key":"49_CR5","unstructured":"Y. Bartal and E. Grove. The harmonic k-server algorithm is competitive. To appear in Journal of the ACM."},{"key":"49_CR6","doi-asserted-by":"crossref","unstructured":"S. Ben-David, A. Borodin, R. M. Karp, G. Tardos, and A. Widgerson. On the power of randomization in on-line algorithms. In Proc. 22nd Symp. Theory of Computing, pages 379\u2013386, 1990.","DOI":"10.1145\/100216.100268"},{"key":"49_CR7","doi-asserted-by":"crossref","unstructured":"A. Blum, H. Karloff, Y. Rabani, and M. Saks. A decomposition theorem and lower bounds for randomized server problems. In Proc. 33rd Symp. Foundations of Computer Science, pages 197\u2013207, 1992.","DOI":"10.1109\/SFCS.1992.267772"},{"key":"49_CR8","unstructured":"A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998."},{"key":"49_CR9","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1137\/0404017","volume":"4","author":"M. Chrobak","year":"1991","unstructured":"M. Chrobak, H. Karloff, T. H. Payne, and S. Vishwanathan. New results on server problems. SIAM Journal on Discrete Mathematics, 4:172\u2013181, 1991.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"49_CR10","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1016\/0196-6774(91)90035-W","volume":"12","author":"M. Chrobak","year":"1991","unstructured":"M. Chrobak and L. L. Larmore. On fast algorithms for two servers. Journal of Algorithms, 12:607\u2013614, 1991.","journal-title":"Journal of Algorithms"},{"key":"49_CR11","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1137\/0220008","volume":"20","author":"M. Chrobak","year":"1991","unstructured":"M. Chrobak and L. L. Larmore. An optimal online algorithm for k servers on trees. SIAM Journal on Computing, 20:144\u2013148, 1991.","journal-title":"SIAM Journal on Computing"},{"key":"49_CR12","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1090\/dimacs\/007\/02","volume":"7","author":"M. Chrobak","year":"1992","unstructured":"M. Chrobak and L. L. Larmore. The server problem and on-line games. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 7, pages 11\u201364, 1992.","journal-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science"},{"key":"49_CR13","doi-asserted-by":"crossref","unstructured":"M. Chrobak and L. L. Larmore. Metrical task systems, the server problem, and the work function algorithm. In Online Algorithms: State of the Art, pages 74\u201394. Springer-Verlag, 1998.","DOI":"10.1007\/BFb0029565"},{"issue":"2","key":"49_CR14","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/S0020-0190(97)00099-9","volume":"63","author":"M. Chrobak","year":"1997","unstructured":"M. Chrobak, L. L. Larmore, C. Lund, and N. Reingold. A better lower bound on the competitive ratio of the randomized 2-server problem. Information Processing Letters, 63(2):79\u201383, 1997.","journal-title":"Information Processing Letters"},{"key":"49_CR15","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1145\/174130.174131","volume":"40","author":"D. Coppersmith","year":"1993","unstructured":"D. Coppersmith, P. G. Doyle, P. Raghavan, and M. Snir. Random walks on weighted graphs and applications to on-line algorithms. Journal of the ACM, 40:421\u2013453, 1993.","journal-title":"Journal of the ACM"},{"key":"49_CR16","unstructured":"E. Feuerstein, S. Seiden, and A. S. de Loma. The related server problem. Manuscript, 1999."},{"key":"49_CR17","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(94)90154-6","volume":"130","author":"A. Fiat","year":"1994","unstructured":"A. Fiat and M. Ricklin. Competitive algorithms for the weighted server problem. Theoretical Computer Science, 130:85\u201399, 1994.","journal-title":"Theoretical Computer Science"},{"key":"49_CR18","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1145\/210118.210128","volume":"42","author":"E. Koutsoupias","year":"1995","unstructured":"E. Koutsoupias and C. Papadimitriou. On the k-server conjecture. Journal of the ACM, 42:971\u2013983, 1995.","journal-title":"Journal of the ACM"},{"key":"49_CR19","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0020-0190(96)00010-5","volume":"57","author":"E. Koutsoupias","year":"1996","unstructured":"E. Koutsoupias and C. Papadimitriou. The 2-evader problem. Information Processing Letters, 57:249\u2013252, 1996.","journal-title":"Information Processing Letters"},{"key":"49_CR20","unstructured":"E. Koutsoupias and D. Taylor. Lower bounds for the CNN problem. To appear in STACS 2000 (this volume), 2000."},{"key":"49_CR21","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","volume":"11","author":"M. Manasse","year":"1990","unstructured":"M. Manasse, L. A. McGeoch, and D. Sleator. Competitive algorithms for server problems. Journal of Algorithms, 11:208\u2013230, 1990.","journal-title":"Journal of Algorithms"},{"issue":"6","key":"49_CR22","doi-asserted-by":"publisher","first-page":"816","DOI":"10.1007\/BF01759073","volume":"6","author":"L. McGeoch","year":"1991","unstructured":"L. McGeoch and D. Sleator. A strongly competitive randomized paging algorithm. Algorithmica, 6(6):816\u2013825, 1991.","journal-title":"Algorithmica"},{"key":"49_CR23","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0304-3975(91)90263-2","volume":"84","author":"C. H. Papadimitriou","year":"1991","unstructured":"C. H. Papadimitriou and M. Yannakakis. Shortest paths without a map. Theoretical Computer Science, 84:127\u2013150, 1991.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","STACS 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46541-3_49","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T14:10:20Z","timestamp":1556719820000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46541-3_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671411","9783540465416"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-46541-3_49","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}