{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:37:29Z","timestamp":1725457049881},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540649175"},{"type":"electronic","value":"9783540683117"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0029565","type":"book-chapter","created":{"date-parts":[[2005,12,6]],"date-time":"2005-12-06T09:47:06Z","timestamp":1133862426000},"page":"74-96","source":"Crossref","is-referenced-by-count":15,"title":["Metrical task systems, the server problem and the work function algorithm"],"prefix":"10.1007","author":[{"given":"Marek","family":"Chrobak","sequence":"first","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":[[2005,11,22]]},"reference":[{"issue":"2","key":"4_CR1","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.1993.1054","volume":"106","author":"R. Baeza-Yates","year":"1993","unstructured":"R. Baeza-Yates, J. Culberson, and G. Rawlins. Searching in the plane. Information and Computation, 106(2):234\u2013252, 1993. Preliminary version in Proc. 1st Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science 318, Springer-Verlag, Berlin, 1988, 176\u2013189. Also Tech. Report CS-87-68, University of Waterloo, Department of Computer Science, October, 1987.","journal-title":"Information and Computation"},{"key":"4_CR2","unstructured":"Y. Bartal and E. Grove. The harmonic k-server algorithm is competitive. To appear in Journal of ACM, 1994."},{"key":"4_CR3","unstructured":"P. Berman, H. Karloff, and G. Tardos. A competitive algorithm for three servers. In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 280\u2013290, 1990."},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"A. Borodin, N. Linial, and M. Saks. An optimal online algorithm for metrical task systems. In Proc. 19th Annual ACM Symposium on Theory of Computing, pages 373\u2013382, 1987.","DOI":"10.1145\/28395.28435"},{"key":"4_CR5","unstructured":"W. Burley. Traversing layered graphs using the work function algorithm. Technical Report CS93-319, Department of Computer Science and Engineering, University of California at San Diego, 1993."},{"key":"4_CR6","doi-asserted-by":"crossref","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. Also in Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, 1990, pp. 291\u2013300.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"4_CR7","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0404029","volume":"4","author":"M. Chrobak","year":"1991","unstructured":"M. Chrobak and L. L. Larmore. A new approach to the server problem. SIAM Journal on Discrete Mathematics, 4:323\u2013328, 1991.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"4_CR8","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":"4_CR9","unstructured":"M. Chrobak and L. L. Larmore. Metrical service systems: Deterministic strategies. Technical Report UCR-CS-93-1, Department of Computer Science, University of California at Riverside, 1992. Submitted for publication in a journal."},{"key":"4_CR10","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":"4_CR11","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/jagm.1994.1011","volume":"16","author":"M. Chrobak","year":"1994","unstructured":"M. Chrobak and L. L. Larmore. Generosity helps or an 11-competitive algorithm for three servers. Journal of Algorithms, 16:234\u2013263, 1994. Also in Proceedings of ACM\/SIAM Symposium on Discrete Algorithms, 1992, 196\u2013202.","journal-title":"Journal of Algorithms"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"X. Deng and C. Papadimitriou. Exploring an unknown graph. In Proc. 31st IEEE Symp. Foundations of Computer Science, pages 355\u2013361, 1990.","DOI":"10.1109\/FSCS.1990.89554"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"A. Fiat, D. Foster, H. Karloff, Y. Rabani, Y. Ravid, and S. Vishwanathan. Competitive algorithms for layered graph traversal. In Proc. 32nd IEEE Symposium on Foundations of Computer Science, pages 288\u2013297, 1991.","DOI":"10.1109\/SFCS.1991.185381"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"A. Fiat, Y. Rabani, and Y. Ravid. Competitive k-server algorithms. In Proc. 22nd IEEE Symposium on Foundations of Computer Science, pages 454\u2013463, 1990.","DOI":"10.1109\/FSCS.1990.89566"},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"E. Grove. The harmonic k-server algorithm is competitive. In Proc. 23rd ACM Symposium on Theory of Computing, pages 260\u2013266, 1991.","DOI":"10.1145\/103418.103448"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"E. Koutsoupias and C. Papadimitriou. On the k-server conjecture. In Proc. 25th Symposium on Theory of Computing, pages 507\u2013511, 1994.","DOI":"10.1145\/195058.195245"},{"key":"4_CR17","doi-asserted-by":"crossref","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":"4_CR18","doi-asserted-by":"crossref","unstructured":"M. Manasse, L. A. McGeoch, and D. Sleator. Competitive algorithms for online problems. In Proc. 20th Annual ACM Symposium on Theory of Computing, pages 322\u2013333, 1988.","DOI":"10.1145\/62212.62243"},{"key":"4_CR19","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"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou and M. Yannakakis. Shortest paths without a map. In 16th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science vol. 372, pages 610\u2013620. Springer-Verlag, 1989.","DOI":"10.1007\/BFb0035787"},{"key":"4_CR21","unstructured":"H. Ramesh. On traversing layered graphs on-line. In Proc. 4th Annual ACM-SIAM Symp. on Discrete Algorithms, pages 412\u2013421, 1993."}],"container-title":["Lecture Notes in Computer Science","Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0029565","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T07:17:16Z","timestamp":1586589436000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029565"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540649175","9783540683117"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/bfb0029565","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}