{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:14:28Z","timestamp":1763468068028},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540616801"},{"type":"electronic","value":"9783540706670"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61680-2_72","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T22:11:22Z","timestamp":1330294282000},"page":"419-430","source":"Crossref","is-referenced-by-count":10,"title":["Competitive analysis of randomized paging algorithms"],"prefix":"10.1007","author":[{"given":"Dimitris","family":"Achlioptas","sequence":"first","affiliation":[]},{"given":"Marek","family":"Chrobak","sequence":"additional","affiliation":[]},{"given":"John","family":"Noga","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,6]]},"reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"A. Borodin, S. Irani, P. Raghavan, and B. Schieber. Competitive paging with locality of reference. In Proc. 23rd ACM Symposium on Theory of Computing, pages 249\u2013259, 1991. To appear in Journal of Computer and System Sciences.","DOI":"10.1145\/103418.103422"},{"key":"31_CR2","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":"31_CR3","unstructured":"M. Chrobak and L. L. Larmore. Metrical service systems: Randomized strategies. manuscript, 1992."},{"key":"31_CR4","doi-asserted-by":"crossref","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":"31_CR5","unstructured":"M. Chrobak, L. L. Larmore, N. Reingold, and J. Westbrook. Page migration algorithms using work functions. Technical Report YALE\/DCS\/RR-910, Department of Yale University, 1992. Submitted for journal publication."},{"key":"31_CR6","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1016\/0196-6774(91)90041-V","volume":"12","author":"A. Fiat","year":"1991","unstructured":"A. Fiat, R. Karp, M. Luby, L. A. McGeoch, D. Sleator, and N.E. Young. Competitive paging algorithms. Journal of Algorithms, 12:685\u2013699, 1991.","journal-title":"Journal of Algorithms"},{"key":"31_CR7","unstructured":"S. Irani, A. Karlin, and S. Phillips. Strongly competitive algorithms for paging with locality of reference. In 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 228\u2013236, 1992."},{"key":"31_CR8","doi-asserted-by":"crossref","unstructured":"A. Karlin, S. Phillips, and P. Raghavan. Markov paging. In Proc. 33rd IEEE Symposium on Foundations of Computer Science, pages 208\u2013217, 1992.","DOI":"10.1109\/SFCS.1992.267771"},{"key":"31_CR9","doi-asserted-by":"crossref","unstructured":"E. Koutsoupias and C. Papadimitriou. Beyond competitive analysis. In Proc. 25th Symposium on Foundations of Computer Science, pages 394\u2013400, 1994.","DOI":"10.1109\/SFCS.1994.365677"},{"key":"31_CR10","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":"31_CR11","doi-asserted-by":"crossref","unstructured":"H. Kuhn. Extensive games and the problem of information. In H. Kuhn and A. Tucker, editors, Contributions to the Theory of Games, pages 193\u2013216. Princeton University Press, 1953.","DOI":"10.1515\/9781400881970-012"},{"key":"31_CR12","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. Also in Proc. 20th Annual ACM Symposium on Theory of Computing, 1988, pp. 322\u2013333.","journal-title":"Journal of Algorithms"},{"key":"31_CR13","doi-asserted-by":"crossref","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. J. Algorithms, 6:816\u2013825, 1991.","journal-title":"J. Algorithms"},{"key":"31_CR14","doi-asserted-by":"crossref","unstructured":"P. Raghavan and M. Snir. Memory versus randomization in online algorithms. In 16th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science vol. 372, pages 687\u2013703. Springer-Verlag, 1989.","DOI":"10.1007\/BFb0035792"},{"key":"31_CR15","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D. Sleator","year":"1985","unstructured":"D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28:202\u2013208, 1985.","journal-title":"Communications of the ACM"},{"key":"31_CR16","unstructured":"N. Young. The k-server dual and loose competitiveness for paging. Algorithmica, 1991. To appear. Rewritten version of \u201cOn-line caching as cache size varies\u201d, in The 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, 241\u2013250, 1991."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61680-2_72.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:09:14Z","timestamp":1605647354000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61680-2_72"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540616801","9783540706670"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-61680-2_72","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}