{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:00:14Z","timestamp":1725494414593},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540648482"},{"type":"electronic","value":"9783540685302"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-68530-8_21","type":"book-chapter","created":{"date-parts":[[2007,11,8]],"date-time":"2007-11-08T17:14:16Z","timestamp":1194542056000},"page":"247-258","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A Randomized Algorithm for Two Servers on the Line (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Yair","family":"Bartal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Chrobak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lawrence L.","family":"Larmore","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,3,15]]},"reference":[{"key":"21_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":"Dimitris Achlioptas, Marek Chrobak, and John 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":"21_CR2","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0020-0190(95)00142-Y","volume":"56","author":"S. Albers","year":"1995","unstructured":"Susanne Albers, Bernhard von Stengel, and Ralph Werchner. A combined bit and timestamp algorithm for the list update problem. Information Processing Letters, 56:135\u2013139, 1995.","journal-title":"Information Processing Letters"},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"Yair Bartal, Avrim Blum, Carl Burch, and Andrew 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":"21_CR4","doi-asserted-by":"crossref","unstructured":"Avrim Blum, Howard Karloff, Yuval Rabani, and Michael 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":"21_CR5","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1287\/moor.10.4.585","volume":"10","author":"A. R. Calderbank","year":"1985","unstructured":"A. R. Calderbank, Edward G. Coffman, and Leopold Flatto. Sequencing problems in two-server systems. Mathematics of Operations Research, 10:585\u2013598, 1985.","journal-title":"Mathematics of Operations Research"},{"key":"21_CR6","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1137\/0404017","volume":"4","author":"M. Chrobak","year":"1991","unstructured":"Marek Chrobak, Howard Karloff, Tom H. Payne, and Sundar Vishwanathan. New results on server problems. SIAM Journal on Discrete Mathematics, 4:172\u2013181, 1991.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"21_CR7","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1137\/0220008","volume":"20","author":"M. Chrobak","year":"1991","unstructured":"Marek Chrobak and Lawrence 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":"21_CR8","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1090\/dimacs\/007\/02","volume":"7","author":"M. Chrobak","year":"1992","unstructured":"Marek Chrobak and Lawrence 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"},{"issue":"2","key":"21_CR9","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/S0020-0190(97)00099-9","volume":"63","author":"M. Chrobak","year":"1997","unstructured":"Marek Chrobak, Lawrence L. Larmore, Carsten Lund, and Nick 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":"21_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/3-540-60220-8_59","volume-title":"Proc. 4th Workshop on Algorithms and Data Structures","author":"S. Irani","year":"1995","unstructured":"Sandy Irani and Steve Seiden. Randomized algorithms for metrical task systems. In Proc. 4th Workshop on Algorithms and Data Structures, volume 955 of Lecture Notes in Computer Science, pages 159\u2013170. Springer, 1995."},{"key":"21_CR11","unstructured":"Anna Karlin, Mark Manasse, Lyle McGeoch, and Susan Owicki. Randomized competitive algorithms for non-uniform problems. In Proc. 1st Symp. on Discrete Algorithms, pages 301\u2013309, 1990."},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Elias Koutsoupias and Christos Papadimitriou. On the k-server conjecture. In Proc. 26th Symp. Theory of Computing, pages 507\u2013511, 1994.","DOI":"10.1145\/195058.195245"},{"key":"21_CR13","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1145\/210118.210128","volume":"42","author":"E. Koutsoupias","year":"1995","unstructured":"Elias Koutsoupias and Christos Papadimitriou. On the k-server conjecture. Journal of the ACM, 42:971\u2013983, 1995.","journal-title":"Journal of the ACM"},{"key":"21_CR14","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0020-0190(96)00010-5","volume":"57","author":"E. Koutsoupias","year":"1996","unstructured":"Elias Koutsoupias and Christos Papadimitriou. The 2-evader problem. Information Processing Letters, 57:249\u2013252, 1996.","journal-title":"Information Processing Letters"},{"key":"21_CR15","unstructured":"Carsten Lund and Nick Reingold. Linear programs for randomized on-line algorithms. In Proc. 5th Symp. on Discrete Algorithms, pages 382\u2013391, 1994."},{"key":"21_CR16","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","volume":"11","author":"M. Manasse","year":"1990","unstructured":"Mark Manasse, Lyle A. McGeoch, and Daniel Sleator. Competitive algorithms for server problems. Journal of Algorithms, 11:208\u2013230, 1990.","journal-title":"Journal of Algorithms"},{"key":"21_CR17","doi-asserted-by":"publisher","first-page":"816","DOI":"10.1007\/BF01759073","volume":"6","author":"L. McGeoch","year":"1991","unstructured":"Lyle McGeoch and Daniel Sleator. A strongly competitive randomized paging algorithm. Journal of Algorithms, 6:816\u2013825, 1991.","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA\u2019 98"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-68530-8_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T11:03:28Z","timestamp":1558263808000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-68530-8_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648482","9783540685302"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-68530-8_21","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]},"assertion":[{"value":"15 March 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}