{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T12:05:29Z","timestamp":1773921929663,"version":"3.50.1"},"reference-count":17,"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\/bf01294260","type":"journal-article","created":{"date-parts":[[2005,3,25]],"date-time":"2005-03-25T03:39:14Z","timestamp":1111721954000},"page":"2-14","source":"Crossref","is-referenced-by-count":174,"title":["On the power of randomization in on-line algorithms"],"prefix":"10.1007","volume":"11","author":[{"given":"S.","family":"Ben-David","sequence":"first","affiliation":[]},{"given":"A.","family":"Borodin","sequence":"additional","affiliation":[]},{"given":"R.","family":"Karp","sequence":"additional","affiliation":[]},{"given":"G.","family":"Tardos","sequence":"additional","affiliation":[]},{"given":"A.","family":"Wigderson","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","unstructured":"P. Berman, H. J. Karloff, and G. Tardos. A competitive three-server algorithm. Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 280?290, Jan. 1990."},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"A. Borodin, N. Linial, and M. Saks. An optimal on-line algorithm for metrical task systems. Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages 373?382, New York City, May 1987.","DOI":"10.1145\/28395.28435"},{"issue":"4","key":"CR3","doi-asserted-by":"crossref","first-page":"743","DOI":"10.1145\/146585.146588","volume":"39","author":"A. Borodin","year":"1992","unstructured":"A. Borodin, N. Linial, and M. Saks. An optimal on-line algorithm for metrical task systems.J. Assoc. Comput. Mach., 39(4):743?763, 1992.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR4","unstructured":"M. Chrobak, H. Karloff, T. Payne, and S. Vishwanathan. New results on server problems.Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 291?300, Jan. 1990. To appear inSIAM J. Discrete Math."},{"key":"CR5","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.Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 369?378, Baltimore, MD, May 1990.","DOI":"10.1145\/100216.100266"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"X. Deng, and S. Mahajan. Randomization vs. computability in on-line problems.Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 289?298, New Orleans, LA, May 1991.","DOI":"10.1145\/103418.103451"},{"key":"CR7","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. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator, and N. E. Young. Competitive paging algorithms.J. Algorithms, 12:685?699, 1991.","journal-title":"J. Algorithms"},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"A. Fiat, Y. Rabani, and Y. Ravid. Competitive K-server algorithms.Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pages 454?463, St. Louis, MO, Oct. 1990.","DOI":"10.1109\/FSCS.1990.89566"},{"key":"CR9","series-title":"Annals of Mathematics Studies, 28","first-page":"245","volume-title":"Contributions to the Theory of Games, Vol. II","author":"D. Gale","year":"1953","unstructured":"D. Gale and F. M. Stewart.Infinite games with perfect information. In W. H. Kuhn and A. W. Tucker, editors,Contributions to the Theory of Games, Vol. II, pages 245?266. Annals of Mathematics Studies, 28, Princeton University Press, Princeton, NJ, 1953."},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"E. Grove. The harmonick-server algorithm is competitive.Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 260?266, New Orleans, LA, May 1991.","DOI":"10.1145\/103418.103448"},{"issue":"1","key":"CR11","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/BF01762111","volume":"3","author":"A. R. Karlin","year":"1988","unstructured":"A. R. Karlin, M. S. Manasse, L. Rudolph, and D. D. Sleator. Competitive snoopy caching.Algorithmica, 3(1):79?119, 1988.","journal-title":"Algorithmica"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","volume":"11","author":"M. S. Manasse","year":"1990","unstructured":"M. S. Manasse, L. A. McGeoch, and D. D. Sleator. Competitive algorithms for on-line problems.J. Algorithms, 11:208?230, 1990.","journal-title":"J. Algorithms"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"363","DOI":"10.2307\/1971035","volume":"102","author":"D. A. Martin","year":"1975","unstructured":"D. A. Martin. Borel determinacy.Ann. of Math., 102:363?371, 1975.","journal-title":"Ann. of Math."},{"issue":"6","key":"CR14","doi-asserted-by":"crossref","first-page":"816","DOI":"10.1007\/BF01759073","volume":"6","author":"L. A. McGeoch","year":"1991","unstructured":"L. A. McGeoch and D. D. Sleator. A strongly competitive randomized paging algorithm.Algorithmica, 6(6):816?825, 1991.","journal-title":"Algorithmica"},{"key":"CR15","series-title":"LNCS, 372","first-page":"687","volume-title":"ICALP, Italy, July 1989.Proceedings of the 16th ICALP","author":"P. Raghavan","year":"1990","unstructured":"P. Raghavan and M. Snir. Memory vs. randomization in on-line algorithms. In ICALP, Italy, July 1989.Proceedings of the 16th ICALP, pages 687?703. LNCS, 372, Springer-Verlag, Berlin, 1990."},{"key":"CR16","unstructured":"P. Raghavan and M. Snir. Memory vs. randomization in on-line algorithms. Revised version of the ICALP paper. Submitted toJ. Assoc. Comput. Mach."},{"issue":"2","key":"CR17","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"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01294260.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01294260\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01294260","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,28]],"date-time":"2024-12-28T19:42:21Z","timestamp":1735414941000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01294260"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,1]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1994,1]]}},"alternative-id":["BF01294260"],"URL":"https:\/\/doi.org\/10.1007\/bf01294260","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,1]]}}}