{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T22:33:49Z","timestamp":1772490829012,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1994,1]]},"DOI":"10.1007\/bf01294261","type":"journal-article","created":{"date-parts":[[2005,3,25]],"date-time":"2005-03-25T03:39:14Z","timestamp":1111721954000},"page":"15-32","source":"Crossref","is-referenced-by-count":74,"title":["Randomized competitive algorithms for the list update problem"],"prefix":"10.1007","volume":"11","author":[{"given":"Nick","family":"Reingold","sequence":"first","affiliation":[]},{"given":"Jeffery","family":"Westbrook","sequence":"additional","affiliation":[]},{"given":"Daniel D.","family":"Sleator","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","first-page":"1","volume-title":"Proc. DIMACS Workshop on On-line Algorithms","author":"N. Alon","year":"1991","unstructured":"N. Alon, R. M. Karp, D. Peleg, and D. West. A graph-theoretic game and its application to thek-server problem.Proc. DIMACS Workshop on On-line Algorithms, pages 1?10. American Mathematical Society, Providence, RI, 1991."},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"S. Ben-David, A. Borodin, R. M. Karp, G. T\u00e1rdos, and A. Wigderson. On the power of randomization in on-line algorithms.Proc. 20th ACM Symp. on Theory of Computing, pages 379?386, 1990.","DOI":"10.1145\/100216.100268"},{"key":"CR3","unstructured":"J. L. Bentley, K. L. Clarkson, and D. B. Levine. Fast linear expected-time algorithms for computing maxima and convex hulls.Proc. 1st ACM-SIAM Symp. on Discrete Algorithms, pages 179?187, 1990."},{"issue":"4","key":"CR4","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1145\/3341.3349","volume":"28","author":"J. L. Bentley","year":"1985","unstructured":"J. L. Bentley and C. C. McGeoch. Amortized analyses of self-organizing sequential search heuristics.Comm. ACM, 28(4):404?411, 1985.","journal-title":"Comm. ACM"},{"issue":"4","key":"CR5","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1145\/5684.5688","volume":"29","author":"J. L. Bentley","year":"1986","unstructured":"J. L. Bentley, D. D. Sleator, R. E. Tarjan, and V. Wei. A locally adaptive data compression scheme.Comm. ACM, 29(4):320?330, 1986.","journal-title":"Comm. ACM"},{"key":"CR6","unstructured":"D. L. Black and D. D. Sleator. Competitive algorithms for replication and migration problems. Technical Report CMU-CS-89-201, Department of Computer Science, Carnegie-Mellon University, 1989."},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"A. Borodin, N. Linial, and M. Saks. An optimal on-line algorithm for metrical task systems.Proc. 19th ACM Symp. on Theory of Computing, pages 373?382, 1987.","DOI":"10.1145\/28395.28435"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"697","DOI":"10.2307\/3212792","volume":"10","author":"P. J. Burville","year":"1973","unstructured":"P. J. Burville and J. F. C. Kingman. On a model for storage and search.J. Appl. Probab., 10:697?701, 1973.","journal-title":"J. Appl. Probab."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1016\/0196-6774(91)90035-W","volume":"12","author":"M. Chrobak","year":"1991","unstructured":"M. Chrobak and L. Larmore. On fast algorithms for two servers.J. Algorithms, 12:607?614, 1991.","journal-title":"J. Algorithms"},{"key":"CR10","unstructured":"M. Chrobak, L. L. Larmore, N. Reingold, and J. Westbrook. Optimal multiprocessor migration algorithms using work functions. Technical Report YALEU\/DCS\/TR-897, Department of Computer Science, Yale University, 1991."},{"key":"CR11","volume-title":"Elementary Numerical Analysis, An Algorithmic Approach","author":"S. D. Conte","year":"1980","unstructured":"S. D. Conte and C. de Boor.Elementary Numerical Analysis, An Algorithmic Approach, 3rd edn. McGraw-Hill, New York, 1980.","edition":"3rd edn."},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"D. Coppersmith, P. Doyle, P. Raghavan, and M. Snir. Random walks on weighted graphs, and applications to on-line algorithms.Proc. 20th ACM Symp. on Theory of Computing, pages 369?377, 1990.","DOI":"10.1145\/100216.100266"},{"key":"CR13","doi-asserted-by":"crossref","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. McGeoch, D. D. Sleator, and N. Young. On competitive algorithms for paging problems.J. Algorithms, 12:685?699, 1991.","journal-title":"J. Algorithms"},{"key":"CR14","unstructured":"M. J. Golin. Ph.D. thesis, Department of Computer Science, Princeton University, 1990. Technical Report CS-TR-266-90."},{"issue":"4","key":"CR15","doi-asserted-by":"crossref","first-page":"715","DOI":"10.1137\/0205050","volume":"5","author":"W. J. Hendricks","year":"1976","unstructured":"W. J. Hendricks. An account of self-organizing systems.SIAM J. Comput., 5(4):715?723, 1976.","journal-title":"SIAM J. Comput."},{"key":"CR16","doi-asserted-by":"crossref","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.Inform. Process. Lett., 38:301?306, 1991.","journal-title":"Inform. Process. Lett."},{"key":"CR17","unstructured":"S. Irani, N. Reingold, J. Westbrook, and D. D. Sleator. Randomized algorithms for the list update problem.Proc. 2nd ACM-SIAM Symp. on Discrete Algorithms, pages 251?260, 1991."},{"key":"CR18","unstructured":"A. R. Karlin, M. S. Manasse, L. A. McGeoch, and S. Owicki. Competitive randomized algorithms for non-uniform problems.Proc. 1st ACM-SIAM Symp. on Discrete Algorithms, 1990."},{"issue":"1","key":"CR19","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/BF01762111","volume":"3","author":"A. Karlin","year":"1988","unstructured":"A. Karlin, M. Manasse, L. Rudolph, and D. Sleator. Competitive snoopy caching.Algorithmica, 3(1):79?119, 1988.","journal-title":"Algorithmica"},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"M. Manasse, L. A. McGeoch, and D. Sleator. Competitive algorithms for on-line problems.Proc. 20th ACM Symp. on Theory of Computing, pages 322?333, 1988.","DOI":"10.1145\/62212.62243"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1287\/opre.13.4.609","volume":"13","author":"J. McCabe","year":"1965","unstructured":"J. McCabe. On serial files with relocatable records.Oper. Res., 13:609?618, 1965.","journal-title":"Oper. Res."},{"key":"CR22","unstructured":"P. Raghavan and M. Snir. Memory versus randomization in on-line algorithms. Research Report RC 15622 (No. 69444), IBM T. J. Watson Reseach Center, 1990."},{"key":"CR23","unstructured":"N. Reingold and J. Westbrook. Optimum off-line algorithms for the list update problem. Technical Report YALEU\/DCS\/TR-805, Yale University, 1990."},{"issue":"2","key":"CR24","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1145\/359997.360000","volume":"19","author":"R. Rivest","year":"1976","unstructured":"R. Rivest. On self-organizing sequential search heuristics.Comm. ACM, 19(2):63?67, 1976.","journal-title":"Comm. ACM"},{"issue":"2","key":"CR25","doi-asserted-by":"crossref","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.Comm. ACM, 28(2):202?208, 1985.","journal-title":"Comm. ACM"},{"key":"CR26","first-page":"135","volume-title":"Proc. DIMACS Workshop on On-Line Algorithms","author":"J. Westbrook","year":"1991","unstructured":"J. Westbrook. Randomized algorithms for multiprocessor page migration.Proc. DIMACS Workshop on On-Line Algorithms, pages 135?150. American Mathematical Society, Providence, RI, 1991."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01294261.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01294261\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01294261","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T13:48:34Z","timestamp":1586180914000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01294261"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,1]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1994,1]]}},"alternative-id":["BF01294261"],"URL":"https:\/\/doi.org\/10.1007\/bf01294261","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,1]]}}}