{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T06:01:47Z","timestamp":1783576907244,"version":"3.55.0"},"reference-count":22,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2000,3,1]],"date-time":"2000-03-01T00:00:00Z","timestamp":951868800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4886,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2000,3]]},"DOI":"10.1016\/s0304-3975(98)00116-9","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T20:39:08Z","timestamp":1027629548000},"page":"203-218","source":"Crossref","is-referenced-by-count":82,"title":["Competitive analysis of randomized paging algorithms"],"prefix":"10.1016","volume":"234","author":[{"given":"Dimitris","family":"Achlioptas","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marek","family":"Chrobak","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Noga","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(98)00116-9_BIB1","doi-asserted-by":"crossref","unstructured":"A. Borodin, S. Irani, P. Raghavan, B. Schieber, Competitive paging with locality of reference, in: Proc. 23rd ACM Symp. on Theory of Computing, 1991, pp. 249\u2013259.","DOI":"10.1145\/103418.103422"},{"issue":"2","key":"10.1016\/S0304-3975(98)00116-9_BIB2","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1006\/jcss.1995.1021","article-title":"Competitive paging with locality of reference","volume":"50","author":"Borodin","year":"1995","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(98)00116-9_BIB3","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1137\/0220008","article-title":"An optimal online algorithm for k servers on trees","volume":"20","author":"Chrobak","year":"1991","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(98)00116-9_BIB4","unstructured":"M. Chrobak, L.L. Larmore, Metrical service systems: randomized strategies. manuscript, 1992a."},{"key":"10.1016\/S0304-3975(98)00116-9_BIB5","unstructured":"M. Chrobak, L.L. Larmore, Generosity helps or an 11-competitive algorithm for three servers, J. Algorithms 16 (1994) 234\u2013263; also in Proc. ACM-SIAM Symp. on Discrete Algorithms, 1992b, pp. 196\u2013202."},{"key":"10.1016\/S0304-3975(98)00116-9_BIB6","doi-asserted-by":"crossref","unstructured":"M. Chrobak, L.L. Larmore, N. Reingold, J. Westbrook, Page migration algorithms using work functions, Tech. Report YALE\/DCS\/RR-910, Department of Computer Science, Yale University, 1992, J. Algorithms, to appear.","DOI":"10.1007\/3-540-57568-5_272"},{"key":"10.1016\/S0304-3975(98)00116-9_BIB7","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1016\/0196-6774(91)90041-V","article-title":"Competitive paging algorithms","volume":"12","author":"Fiat","year":"1991","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(98)00116-9_BIB8","doi-asserted-by":"crossref","unstructured":"S. Irani, S. Seiden, Randomized algorithms for metrical task systems, in: Proc. 4th Workshop on Algorithms and Data Structures, 1995, pp. 159\u2013170.","DOI":"10.1007\/3-540-60220-8_59"},{"key":"10.1016\/S0304-3975(98)00116-9_BIB9","unstructured":"S. Irani, A. Karlin, S. Phillips, Strongly competitive algorithms for paging with locality of reference, in: 3rd Annu. ACM-SIAM Symp. on Discrete Algorithms, 1992, pp. 228\u2013236."},{"key":"10.1016\/S0304-3975(98)00116-9_BIB10","doi-asserted-by":"crossref","unstructured":"A. Karlin, S. Phillips, P. Raghavan, Markov paging, in: Proc. 33rd IEEE Symp. on Foundations of Computer Science, 1992, pp. 208\u2013217.","DOI":"10.1109\/SFCS.1992.267771"},{"key":"10.1016\/S0304-3975(98)00116-9_BIB11","doi-asserted-by":"crossref","unstructured":"E. Koutsoupias, C. Papadimitriou, Beyond competitive analysis, in: Proc. 35th Symp. on Foundations of Computer Science, 1994a, pp. 394\u2013400.","DOI":"10.1109\/SFCS.1994.365677"},{"key":"10.1016\/S0304-3975(98)00116-9_BIB12","doi-asserted-by":"crossref","unstructured":"E. Koutsoupias, C. Papadimitriou, On the k-server conjecture, in: Proc. 26th Symp. on Theory of Computing, 1994, pp. 507\u2013511.","DOI":"10.1145\/195058.195245"},{"issue":"5","key":"10.1016\/S0304-3975(98)00116-9_BIB13","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1145\/210118.210128","article-title":"On the k-server conjecture","volume":"42","author":"Koutsoupias","year":"1995","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0304-3975(98)00116-9_BIB14","series-title":"Contributions to the Theory of Games","first-page":"193","article-title":"Extensive games and the problem of information","author":"Kuhn","year":"1953"},{"key":"10.1016\/S0304-3975(98)00116-9_BIB15","unstructured":"C. Lund, N. Reingold, Linear programs for randomized on-line algorithms, in: Proc. 5th ACM-SIAM Symp. on Discrete Algorithms, 1994a, pp. 382\u2013391."},{"key":"10.1016\/S0304-3975(98)00116-9_BIB16","doi-asserted-by":"crossref","unstructured":"C. Lund, N. Reingold, J. Westbrook, D. Yan, On-line distributed data management, in: Proc. European Symp. on Algorithms, 1994b, pp. 202\u2013214.","DOI":"10.1007\/BFb0049409"},{"key":"10.1016\/S0304-3975(98)00116-9_BIB17","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","article-title":"Competitive algorithms for server problems","volume":"11","author":"Manasse","year":"1990","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(98)00116-9_BIB18","doi-asserted-by":"crossref","first-page":"816","DOI":"10.1007\/BF01759073","article-title":"A strongly competitive randomized paging algorithm","volume":"6","author":"McGeoch","year":"1991","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(98)00116-9_BIB19","first-page":"687","article-title":"Memory versus randomization in online algorithms","volume":"vol. 372","author":"Raghavan","year":"1989"},{"key":"10.1016\/S0304-3975(98)00116-9_BIB20","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","article-title":"Amortized efficiency of list update and paging rules","volume":"28","author":"Sleator","year":"1985","journal-title":"Communications of the ACM"},{"key":"10.1016\/S0304-3975(98)00116-9_BIB21","unstructured":"N. Young, On-line caching as cache size varies, in: Proc. 2nd Ann. ACM-SIAM Symp. on Discrete Algorithms, 1991, pp. 241\u2013250."},{"issue":"6","key":"10.1016\/S0304-3975(98)00116-9_BIB22","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/BF01189992","article-title":"The k-server dual and loose competitiveness for paging","volume":"11","author":"Young","year":"1994","journal-title":"Algorithmica"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397598001169?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397598001169?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,5]],"date-time":"2024-12-05T08:27:14Z","timestamp":1733387234000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397598001169"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,3]]},"references-count":22,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2000,3]]}},"alternative-id":["S0304397598001169"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(98)00116-9","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2000,3]]}}}