{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:13:04Z","timestamp":1787505184551,"version":"build-2736575974"},"reference-count":20,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2002,9,1]],"date-time":"2002-09-01T00:00:00Z","timestamp":1030838400000},"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":3972,"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":[[2002,9]]},"DOI":"10.1016\/s0304-3975(01)00253-5","type":"journal-article","created":{"date-parts":[[2002,10,9]],"date-time":"2002-10-09T15:39:34Z","timestamp":1034177974000},"page":"393-418","source":"Crossref","is-referenced-by-count":4,"title":["On list update and work function algorithms"],"prefix":"10.1016","volume":"287","author":[{"given":"Eric J.","family":"Anderson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kirsten","family":"Hildrum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anna R.","family":"Karlin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"April","family":"Rasala","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Saks","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(01)00253-5_BIB1","doi-asserted-by":"crossref","first-page":"682","DOI":"10.1137\/S0097539794277858","article-title":"Improved randomized on-line algorithms for the list update problem","volume":"27","author":"Albers","year":"1998","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(01)00253-5_BIB2","unstructured":"S. Albers, Private communication."},{"key":"10.1016\/S0304-3975(01)00253-5_BIB3","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0020-0190(95)00142-Y","article-title":"A combined BIT and TIMESTAMP algorithm for the list update problem","volume":"56","author":"Albers","year":"1995","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(01)00253-5_BIB4","doi-asserted-by":"crossref","unstructured":"S. Albers, J. Westbrook, Self-organizing data structures, in: Online Algorithms: The State of the Art, Fiat-Woeginger, Springer, Berlin, 1998.","DOI":"10.1007\/BFb0029563"},{"issue":"4","key":"10.1016\/S0304-3975(01)00253-5_BIB5","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1145\/3341.3349","article-title":"Amortized analysis of self-organizing sequential search heuristics","volume":"28","author":"Bentley","year":"1985","journal-title":"Commun. ACM"},{"key":"10.1016\/S0304-3975(01)00253-5_BIB6","first-page":"46","article-title":"An optimal online algorithm for metrical task systems","volume":"52","author":"Borodin","year":"1995","journal-title":"J. ACM"},{"issue":"3","key":"10.1016\/S0304-3975(01)00253-5_BIB7","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1006\/jagm.1996.0024","article-title":"Traversing layered graphs using the work function algorithm","volume":"20","author":"Burley","year":"1996","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(01)00253-5_BIB8","unstructured":"W. Burley, S. Irani, On algorithm design for metrical task systems, ACM-SIAM Symp. on Discrete Algorithms, 1995."},{"key":"10.1016\/S0304-3975(01)00253-5_BIB9","doi-asserted-by":"crossref","unstructured":"M. Chrobak, L. Larmore, The server problem and on-line games, On-Line Algorithms, Proc. DIMACS Workshop, DIMACS Series in Discrete Mathematics and Computer Science, Vol. 7, 1991, pp. 11\u201364.","DOI":"10.1090\/dimacs\/007\/02"},{"key":"10.1016\/S0304-3975(01)00253-5_BIB10","unstructured":"M. Chrobak, J. Noga, Competitive algorithms for multilevel caching and relaxed list update, Proc. of ACM\u2013SIAM Symp. on Discrete Algorithms, 1998."},{"key":"10.1016\/S0304-3975(01)00253-5_BIB11","unstructured":"R. El-Yaniv, There are infinitely many competitive-optimal online list accessing algorithms, Discussion paper from The Center for Rationality and Interactive Decision Making, Hebrew University."},{"issue":"6","key":"10.1016\/S0304-3975(01)00253-5_BIB12","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0020-0190(91)90086-W","article-title":"Two results on the list update problem","volume":"38","author":"Irani","year":"1991","journal-title":"Inform. Process. Lett."},{"issue":"5","key":"10.1016\/S0304-3975(01)00253-5_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. ACM"},{"key":"10.1016\/S0304-3975(01)00253-5_BIB14","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"},{"issue":"2","key":"10.1016\/S0304-3975(01)00253-5_BIB15","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0020-0190(96)00144-5","article-title":"Off-line algorithms for the list update problem","volume":"60","author":"Reingold","year":"1996","journal-title":"Informat. Process. Lett."},{"key":"10.1016\/S0304-3975(01)00253-5_BIB16","unstructured":"S. Roura, C. Martinez, On the competitiveness of the Move-to-front rule, Technical Report LSI-96-63-R, Technical University of Catalonia, 1997."},{"key":"10.1016\/S0304-3975(01)00253-5_BIB17","doi-asserted-by":"crossref","unstructured":"F. Schulz, Two new families of list update algorithms, Proc. Ninth Int. Symp., ISAAC, Lecture Notes in Computer Science, Vol. 1533, Springer, Berlin, 1998, pp. 99\u2013108.","DOI":"10.1007\/3-540-49381-6_12"},{"key":"10.1016\/S0304-3975(01)00253-5_BIB18","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":"Commun. ACM"},{"key":"10.1016\/S0304-3975(01)00253-5_BIB19","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1145\/3828.3835","article-title":"Self-adjusting binary search trees","volume":"32","author":"Sleatorm","year":"1985","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(01)00253-5_BIB20","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0020-0190(93)90150-8","article-title":"A lower bound for randomized list update algorithms","volume":"47","author":"Teia","year":"1993","journal-title":"Inform. Process. Lett."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501002535?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501002535?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,8]],"date-time":"2020-03-08T05:16:22Z","timestamp":1583644582000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397501002535"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,9]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2002,9]]}},"alternative-id":["S0304397501002535"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(01)00253-5","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2002,9]]}}}