{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T19:03:51Z","timestamp":1794337431845,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540649175","type":"print"},{"value":"9783540683117","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0029562","type":"book-chapter","created":{"date-parts":[[2005,12,6]],"date-time":"2005-12-06T09:47:06Z","timestamp":1133862426000},"page":"1-12","source":"Crossref","is-referenced-by-count":22,"title":["Competitive analysis of algorithms"],"prefix":"10.1007","author":[{"given":"Amos","family":"Fiat","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gerhard J.","family":"Woeginger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,11,22]]},"reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01294260","volume":"11","author":"S. Ben-David","year":"1994","unstructured":"S. Ben-David, A. Borodin, R.M. Karp, G. Tardos, and A. Wigderson. On the power of randomization in on-line algorithms. Algorithmica, 11:2\u201314, 1994.","journal-title":"Algorithmica"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"A. Borodin, N. Linial, and M. Saks. An optimal online algorithm for metrical task systems. In Proc. 19th Annual ACM Symposium on Theory of Computing, pages 373\u2013382, 1987.","DOI":"10.1145\/28395.28435"},{"issue":"1","key":"1_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.1467-9965.1991.tb00002.x","volume":"1","author":"T.M. Cover","year":"1991","unstructured":"T.M. Cover. Universal portfolios. Mathematical Finance, 1(1):1\u201329, January 1991.","journal-title":"Mathematical Finance"},{"key":"1_CR4","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R. L. Graham","year":"1966","unstructured":"R. L. Graham. Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45:1563\u20131581, 1966.","journal-title":"Bell System Technical Journal"},{"key":"1_CR5","volume-title":"PhD thesis","author":"D. S. Johnson","year":"1973","unstructured":"D. S. Johnson. Near-optimal bin packing algorithms. PhD thesis, MIT, Cambridge, MA, 1973."},{"key":"1_CR6","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1016\/S0022-0000(74)80026-7","volume":"8","author":"D. S. Johnson","year":"1974","unstructured":"D. S. Johnson. Fast algorithms for bin packing. J. Comput. System Sci., 8:272\u2013314, 1974.","journal-title":"J. Comput. System Sci."},{"key":"1_CR7","unstructured":"D. S. Johnson. Private communication, 1998."},{"issue":"1","key":"1_CR8","doi-asserted-by":"publisher","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\u2013119, 1988.","journal-title":"Algorithmica"},{"key":"1_CR9","first-page":"143","volume":"33","author":"H. A. Kierstead","year":"1981","unstructured":"H. A. Kierstead and W. T. Trotter. An extremal problem in recursive combinatorics. Congressus Numerantium, 33:143\u2013153, 1981.","journal-title":"Congressus Numerantium"},{"key":"1_CR10","unstructured":"D.E. Knuth. The Art of Computer Programming; Volume 2: Seminumerical Algorithms. Addison-Wesley, 1st edition, 1968."},{"key":"1_CR11","doi-asserted-by":"crossref","unstructured":"M. Manasse, L. A. McGeoch, and D. Sleator. Competitive algorithms for online problems. In Proc. 20th Annual ACM Symposium on Theory of Computing, pages 322\u2013333, 1988.","DOI":"10.1145\/62212.62243"},{"key":"1_CR12","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0304-3975(91)90263-2","volume":"84","author":"C. H. Papadimitriou","year":"1991","unstructured":"C. H. Papadimitriou and M. Yannakakis. Shortest paths without a map. Theoretical Computer Science, 84:127\u2013150, 1991.","journal-title":"Theoretical Computer Science"},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D. Sleator","year":"1985","unstructured":"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"},{"key":"1_CR14","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D. D. Sleator","year":"1985","unstructured":"Daniel D. Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. Journal of the ACM, 32:652\u2013686, 1985.","journal-title":"Journal of the ACM"},{"key":"1_CR15","first-page":"240","volume":"81","author":"D. R. Woodall","year":"1974","unstructured":"D. R. Woodall. The bay restaurant \u2014 a linear storage problem. American Mathematical Monthly, 81:240\u2013246, 1974.","journal-title":"American Mathematical Monthly"},{"key":"1_CR16","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1145\/322186.322187","volume":"27","author":"A. C. C. Yao","year":"1980","unstructured":"A. C. C. Yao. New algorithms for bin packing. J. Assoc. Comput. Mach., 27:207\u2013227, 1980.","journal-title":"J. Assoc. Comput. Mach."}],"container-title":["Lecture Notes in Computer Science","Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0029562","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T07:17:09Z","timestamp":1586589429000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029562"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540649175","9783540683117"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/bfb0029562","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/bfb0029561","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998]]}}}