{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:40Z","timestamp":1725490240683},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540412557"},{"type":"electronic","value":"9783540409960"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-40996-3_4","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T21:17:32Z","timestamp":1188335852000},"page":"35-46","source":"Crossref","is-referenced-by-count":0,"title":["A New Competitive Analysis of Randomized Caching"],"prefix":"10.1007","author":[{"given":"Ching","family":"Law","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charles E.","family":"Leiserson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,1,29]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"D. Achlioptas, M. Chrobak, and J. Noga. Competitive analysis of randomized paging algorithms. In Annual European Symposium on Algorithms, 1996.","DOI":"10.1007\/3-540-61680-2_72"},{"issue":"2","key":"4_CR2","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1147\/sj.52.0078","volume":"5","author":"L. A. Belady","year":"1966","unstructured":"L. A. Belady. A study of replacement algorithms for virtual storage computers. IBM Systems Journal, 5(2):78\u2013101, 1966.","journal-title":"IBM Systems Journal"},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BF01294264","volume":"11","author":"S. Ben-David","year":"1994","unstructured":"S. Ben-David and A. Borodin. A new measure for the study of on-line algorithms. Algorithmica, 11:73\u201391, 1994.","journal-title":"Algorithmica"},{"key":"4_CR4","unstructured":"Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998."},{"issue":"2","key":"4_CR5","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1006\/jcss.1995.1021","volume":"50","author":"A. Borodin","year":"1995","unstructured":"Allan Borodin, Sandy Irani, Prabhakar Raghavan, and Baruch Schieber. Competitive paging with locality of reference. Journal of Computer and System Sciences, 50(2):244\u2013258, April 1995.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"4_CR6","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1145\/146585.146588","volume":"39","author":"A. Borodin","year":"1992","unstructured":"Allan Borodin, Nathan Linial, and Michael E. Saks. An optimal on-line algorithm for metrical task system. Journal of the ACM, 39(4):745\u2013763, October 1992.","journal-title":"Journal of the ACM"},{"key":"4_CR7","unstructured":"Edward G. Coffman, Jr and Peter J. Denning. Operating Systems Theory. Prentice Hall, 1973."},{"key":"4_CR8","series-title":"Technical Report","volume-title":"Randomized paging algorithms and measures for their performance","author":"E. Dichterman","year":"1991","unstructured":"E. Dichterman. Randomized paging algorithms and measures for their performance. Technical Report 692, Israel Institute of Technology, Haifa, Israel, October 1991."},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"A. Fiat, Y. Rabani, and Y. Ravid. Competitive k-server algorithms. In 31st Annual Symposium on Foundations of Computer Science, pages 454\u2013463, 1990.","DOI":"10.1109\/FSCS.1990.89566"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Amos Fiat and Anna R. Karlin. Randomized and multipointer paging with locality of reference. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 626\u2013634, Las Vegas, Nevada, 29 May-1 June 1995.","DOI":"10.1145\/225058.225280"},{"issue":"4","key":"4_CR11","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1016\/0196-6774(91)90041-V","volume":"12","author":"A. Fiat","year":"1991","unstructured":"Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel D. Sleator, and Neal E. Young. Competitive paging algorithms. Journal of Algorithms, 12(4):685\u2013699, December 1991.","journal-title":"Journal of Algorithms"},{"key":"4_CR12","unstructured":"Michel X. Goemans. Advanced algorithms lecture notes. September 1994."},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"E. F. Grove. The harmonic online K-server algorithm is competitive. In Lyle A. McGeoch and Daniel D. Sleator, editors, On-line Algorithms, volume 7 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 65\u201377. AMS\/ACM, February 1991.","DOI":"10.1090\/dimacs\/007\/03"},{"issue":"3","key":"4_CR14","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1137\/S0097539792236353","volume":"25","author":"S. Irani","year":"1996","unstructured":"Sandy Irani, Anna R. Karlin, and Steven Phillips. Strongly competitive algorithms for paging with locality of reference. SIAM Journal on Computing, 25(3):477\u2013497, June 1996.","journal-title":"SIAM Journal on Computing"},{"key":"4_CR15","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/BF01762111","volume":"3","author":"A. R. Karlin","year":"1988","unstructured":"Anna R. Karlin, Mark S. Manasse, Larry Rudolph, and Daniel Dominic Sleator. Competitive snoopy caching. Algorithmica, 3:77\u2013119, 1988.","journal-title":"Algorithmica"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Elias Koutsoupias and Christos H. Papadimitriou. Beyond competitive analysis. In 35th Annual Symposium on Foundations of Computer Science, pages 394\u2013400, Santa Fe, New Mexico, 20\u201322 November 1994. IEEE.","DOI":"10.1109\/SFCS.1994.365677"},{"issue":"5","key":"4_CR17","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1145\/210118.210128","volume":"42","author":"E. Koutsoupias","year":"1995","unstructured":"Elias Koutsoupias and Christos H. Papadimitriou. On the k-server conjecture. Journal of the ACM, 42(5):971\u2013983, September 1995.","journal-title":"Journal of the ACM"},{"issue":"5","key":"4_CR18","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 H. Papadimitriou. The 2-evader problem. Information Processing Letters, 57(5):249\u2013252, 11 March 1996.","journal-title":"Information Processing Letters"},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"Mark S. Manasse, Lyle A. McGeoch, and Daniel D. Sleator. Competitive algorithms for on-line problems. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 322\u2013333, Chicago, Illinois, 2\u20134 May 1988.","DOI":"10.1145\/62212.62243"},{"key":"4_CR20","volume-title":"Algorithms for Two Graph Problems: Computing Maximum Genus Imbeddings and the Two-Server Problem","author":"L. A. McGeoch","year":"1987","unstructured":"Lyle A. McGeoch. Algorithms for Two Graph Problems: Computing Maximum Genus Imbeddings and the Two-Server Problem. PhD thesis, Carnegie Mellon University, Pittsburgh, 1987."},{"key":"4_CR21","doi-asserted-by":"publisher","first-page":"816","DOI":"10.1007\/BF01759073","volume":"6","author":"L. A. McGeoch","year":"1991","unstructured":"Lyle A. McGeoch and Daniel D. Sleator. A strongly competitive randomized paging algorithm. Algorithmica, 6:816\u2013825, 1991.","journal-title":"Algorithmica"},{"issue":"6","key":"4_CR22","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1147\/rd.386.0683","volume":"38","author":"P. Raghavan","year":"1994","unstructured":"Prabhakar Raghavan and Marc Snir. Memory versus randomization in on-line algorithms. IBM Journal of Research and Development, 38(6):683\u2013707, November 1994.","journal-title":"IBM Journal of Research and Development"},{"issue":"2","key":"4_CR23","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D. D. Sleator","year":"1985","unstructured":"Daniel D. Sleator and Robert E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202\u2013208, February 1985.","journal-title":"Communications of the ACM"},{"key":"4_CR24","doi-asserted-by":"crossref","unstructured":"Eric Torng. A unified analysis of paging and caching. In 36th Annual Symposium on Foundations of Computer Science, pages 194\u2013203, Milwaukee, Wisconsin, 23\u201325 October 1995. IEEE.","DOI":"10.1109\/SFCS.1995.492476"},{"key":"4_CR25","unstructured":"Neal E. Young. On-line caching as cache size varies. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 241\u2013250, San Francisco, California, 28\u201330 January 1991."},{"issue":"6","key":"4_CR26","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/BF01189992","volume":"11","author":"N. E. Young","year":"1994","unstructured":"Neal E. Young. The k-server dual and loose competitiveness for paging. Algorithmica, 11(6):525\u2013541, June 1994.","journal-title":"Algorithmica"},{"key":"4_CR27","unstructured":"Neal E. Young. On-line file caching. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-98), pages 82\u201386, New York,January 25\u201327 1998. ACM Press."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-40996-3_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T13:25:57Z","timestamp":1556803557000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-40996-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540412557","9783540409960"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-40996-3_4","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}