{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:41:59Z","timestamp":1725493319277},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662518"},{"type":"electronic","value":"9783540484813"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48481-7_26","type":"book-chapter","created":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T19:49:40Z","timestamp":1193514580000},"page":"289-300","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On List Update and Work Function Algorithms"],"prefix":"10.1007","author":[{"given":"Eric J.","family":"Anderson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kris","family":"Hildrum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anna R.","family":"Karlin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"April","family":"Rasala","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Saks","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,1,14]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"S. Albers and J. Westbrook. Self-organizing data structures. In Online Algorithms: The State of the Art, Fiat-Woeginger, Springer, 1998.","DOI":"10.1007\/BFb0029563"},{"key":"26_CR2","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D. D. Sleator","year":"1985","unstructured":"D. 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"},{"issue":"4","key":"26_CR3","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1145\/3341.3349","volume":"28","author":"J. L. Bentley","year":"1985","unstructured":"J. L. Bentley and C. McGeoch. Amortized analysis of self-organizing sequential search heuristics. Communications of the ACM, 28(4):404\u2013411, 1985.","journal-title":"Communications of the ACM"},{"key":"26_CR4","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1137\/S0097539794277858","volume":"27","author":"S. Albers","year":"1998","unstructured":"S. Albers. Improved randomized on-line algorithms for the list update problem. SIAM Journal on Computing, 27: 682\u2013693, 1998.","journal-title":"SIAM Journal on Computing"},{"key":"26_CR5","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":"2","key":"26_CR6","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0020-0190(96)00144-5","volume":"60","author":"N. Reingold","year":"1996","unstructured":"N. Reingold and J. Westbrook. Off-line algorithms for the list update problem. Information Processing Letters, 60(2):75\u201380, 1996.","journal-title":"Information Processing Letters"},{"issue":"6","key":"26_CR7","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0020-0190(91)90086-W","volume":"38","author":"S. Irani","year":"1991","unstructured":"S. Irani. Two results on the list update problem. Information Processing Letters, 38(6):301\u2013306, 1991.","journal-title":"Information Processing Letters"},{"key":"26_CR8","first-page":"46","volume":"52","author":"A. Borodin","year":"1985","unstructured":"A. Borodin, N. Linial, and M. Saks. An optimal online algorithm for metrical task systems. Journal of the ACM, 52:46\u201352, 1985.","journal-title":"Journal of the ACM"},{"issue":"5","key":"26_CR9","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1145\/210118.210128","volume":"42","author":"E. Koutsoupias","year":"1995","unstructured":"E. Koutsoupias and C. Papadimitriou. On the k-server conjecture. Journal of the ACM, 42(5): 971\u2013983, September 1995.","journal-title":"Journal of the ACM"},{"key":"26_CR10","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. McGeoch and D. D. Sleator. Competitive algorithms for server problems. Journal of Algorithms, 11:208\u2013230, 1990.","journal-title":"Journal of Algorithms"},{"key":"26_CR11","unstructured":"W. Burley and S. Irani. On algorithm design for metrical task systems. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 1995."},{"key":"26_CR12","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D. D. Sleator","year":"1985","unstructured":"D. D. Sleator and R. E. Tarjan. Self-adjusting binary search trees. Journal of the ACM, 32: 652\u2013686, 1985.","journal-title":"Journal of the ACM"},{"key":"26_CR13","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1090\/dimacs\/007\/02","volume":"7","author":"M. Chrobak","year":"1991","unstructured":"M. Chrobak, L. Larmore. The server problem and on-line games. In On-Line Algorithms, Proceedings of a DIMACS Workshop,Vol 7 of DIMACS Series in Discrete Mathematics and Computer Science, pp. 11\u201364, 1991.","journal-title":"On-Line Algorithms, Proceedings of a DIMACS Workshop"},{"issue":"3","key":"26_CR14","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1006\/jagm.1996.0024","volume":"20","author":"W. R. Burley","year":"1996","unstructured":"W. R. Burley. Traversing layered graphs using the work function algorithm. Journal of Algorithms, 20(3):479\u2013511, 1996.","journal-title":"Journal of Algorithms"},{"key":"26_CR15","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/0020-0190(93)90150-8","volume":"47","author":"B. Teia","year":"1993","unstructured":"B. Teia. Alower bound for randomized list update algorithms. Information Processing Letters, 47:5\u20139, 1993.","journal-title":"Information Processing Letters"},{"key":"26_CR16","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0020-0190(95)00142-Y","volume":"56","author":"S. Albers","year":"1995","unstructured":"S. Albers, B. von Stengel and R. Werchner. A combined BIT and TIMESTAMP algorithm for the list update problem. Information Processing Letters; 56: 135\u2013139, 1995.","journal-title":"Information Processing Letters"},{"key":"26_CR17","unstructured":"S. Albers. Private communication."}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA\u2019 99"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48481-7_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T10:48:08Z","timestamp":1558262888000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48481-7_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662518","9783540484813"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-48481-7_26","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"14 January 2003","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}