{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T05:38:18Z","timestamp":1774417098398,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2009,9,12]],"date-time":"2009-09-12T00:00:00Z","timestamp":1252713600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2012,2]]},"DOI":"10.1007\/s10951-009-0129-5","type":"journal-article","created":{"date-parts":[[2009,9,11]],"date-time":"2009-09-11T13:07:01Z","timestamp":1252674421000},"page":"13-21","source":"Crossref","is-referenced-by-count":24,"title":["Comparing online algorithms for bin packing problems"],"prefix":"10.1007","volume":"15","author":[{"given":"Leah","family":"Epstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lene M.","family":"Favrholdt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens S.","family":"Kohrt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,9,12]]},"reference":[{"issue":"4","key":"129_CR1","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1016\/0196-6774(84)90004-X","volume":"5","author":"S. F. Assman","year":"1984","unstructured":"Assman, S. F., Johnson, D. S., Kleitman, D. J., & Leung, J. Y.-T. (1984). On a dual version of the one-dimensional bin packing problem. Journal of Algorithms, 5(4), 502\u2013525.","journal-title":"Journal of Algorithms"},{"issue":"1","key":"129_CR2","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BF01294264","volume":"11","author":"S. Ben-David","year":"1994","unstructured":"Ben-David, S., & Borodin, A. (1994). A new measure for the study of on-line algorithms. Algorithmica, 11(1), 73\u201391.","journal-title":"Algorithmica"},{"key":"129_CR3","unstructured":"Boyar, J., Ehmsen, M. R., & Larsen, K. S. (2006). Theoretical evidence for the superiority of LRU-2 over LRU for the paging problem. In Approximation and online algorithms (pp.\u00a095\u2013107)."},{"issue":"2","key":"129_CR4","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/1240233.1240245","volume":"3","author":"J. Boyar","year":"2007","unstructured":"Boyar, J., & Favrholdt, L. M. (2007). The relative worst order ratio for online algorithms. ACM Transactions on Algorithms, 3(2), 22.","journal-title":"ACM Transactions on Algorithms"},{"issue":"5","key":"129_CR5","doi-asserted-by":"crossref","first-page":"818","DOI":"10.1016\/j.jcss.2007.03.001","volume":"73","author":"J. Boyar","year":"2007","unstructured":"Boyar, J., Favrholdt, L. M., & Larsen, K. S. (2007). The relative worst order ratio applied to paging. Journal of Computer and System Sciences, 73(5), 818\u2013843.","journal-title":"Journal of Computer and System Sciences"},{"key":"129_CR6","doi-asserted-by":"crossref","unstructured":"Boyar, J., & Medvedev, P. (2008). The relative worst order ratio applied to seat reservation. ACM Transactions on Algorithms, 4(4). Article 48, 22\u00a0pp.","DOI":"10.1145\/1383369.1383379"},{"key":"129_CR7","volume-title":"Handbook of approximation algorithms and metaheuristics","author":"E. G. Coffman Jr.","year":"2007","unstructured":"Coffman, E. G., Jr., & Csirik, J. (2007). Performance guarantees for one-dimensional bin packing. In T. F. Gonzalez (Ed.), Handbook of approximation algorithms and metaheuristics. London: Chapman & Hall. Chap.\u00a032, 18\u00a0pp."},{"issue":"1","key":"129_CR8","first-page":"13","volume":"14","author":"J. Csirik","year":"1999","unstructured":"Csirik, J., Frenk, J. B. G., Labb\u00e9, M., & Zhang, S. (1999). Two simple algorithms for bincovering. Acta Cybernetica, 14(1), 13\u201325.","journal-title":"Acta Cybernetica"},{"key":"129_CR9","volume-title":"Handbook of approximation algorithms and metaheuristics","author":"J. Csirik","year":"2007","unstructured":"Csirik, J., & Leung, J. Y.-T. (2007a). Variable-sized bin packing and bin covering. In T. F. Gonzalez (Ed.), Handbook of approximation algorithms and metaheuristics. London: Chapman & Hall. Chap.\u00a034, 11\u00a0pp."},{"key":"129_CR10","volume-title":"Handbook of approximation algorithms and metaheuristics","author":"J. Csirik","year":"2007","unstructured":"Csirik, J., & Leung, J. Y.-T. (2007b). Variants of classical one-dimensional bin packing. In T. F. Gonzalez (Ed.), Handbook of approximation algorithms and metaheuristics. London: Chapman & Hall. Chap.\u00a033, 13\u00a0pp."},{"key":"129_CR11","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0166-218X(88)90052-2","volume":"21","author":"J. Csirik","year":"1988","unstructured":"Csirik, J., & Totik, V. (1988). On-line algorithms for a dual version of bin packing. Discrete Applied Mathematics, 21, 163\u2013167.","journal-title":"Discrete Applied Mathematics"},{"key":"129_CR12","doi-asserted-by":"crossref","unstructured":"Ehmsen, M. R., Favrholdt, L. M., Kohrt, J. S., & Mihai, R. (2008). Comparing First-Fit and Next-Fit for online edge coloring. In 19th international symposium on algorithms and computation (pp.\u00a089\u201399).","DOI":"10.1007\/978-3-540-92182-0_11"},{"issue":"4","key":"129_CR13","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/s10878-006-9005-9","volume":"12","author":"L. Epstein","year":"2006","unstructured":"Epstein, L., Favrholdt, L. M., & Kohrt, J. S. (2006). Separating online scheduling algorithms with the relative worst order ratio. Journal of Combinatorial Optimization, 12(4), 362\u2013385.","journal-title":"Journal of Combinatorial Optimization"},{"key":"129_CR14","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":"Graham, R. L. (1966). Bounds for certain multiprocessing anomalies. Bell Systems Technical Journal, 45, 1563\u20131581.","journal-title":"Bell Systems Technical Journal"},{"key":"129_CR15","doi-asserted-by":"crossref","unstructured":"Hiller, B., & Vredeveld, T. (2008). Probabilistic analysis of online bin coloring algorithms via stochastic comparison. In Proceedings of the 16th annual European symposium (pp.\u00a0528\u2013539).","DOI":"10.1007\/978-3-540-87744-8_44"},{"issue":"3","key":"129_CR16","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1016\/S0022-0000(74)80026-7","volume":"8","author":"D. S. Johnson","year":"1974","unstructured":"Johnson, D. S. (1974). Fast algorithms for bin packing. Journal of Computer and System Sciences, 8(3), 272\u2013314.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"129_CR17","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1137\/0203025","volume":"3","author":"D. S. Johnson","year":"1974","unstructured":"Johnson, D. S., Demers, A., Ullman, J. D., Garey, M. R., & Graham, R. L. (1974). Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing, 3(4), 299\u2013325.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"129_CR18","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/BF01762111","volume":"3","author":"A. R. Karlin","year":"1988","unstructured":"Karlin, A. R., Manasse, M. S., Rudolph, L., & Sleator, D. D. (1988). Competitive snoopy caching. Algorithmica, 3(1), 79\u2013119.","journal-title":"Algorithmica"},{"key":"129_CR19","unstructured":"Kenyon, C. (1996). Best-fit bin-packing with random order. In Proceedings of the 7th annual ACM-SIAM symposium on discrete algorithms (pp.\u00a0359\u2013364)."},{"issue":"1\u20133","key":"129_CR20","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/j.tcs.2008.05.022","volume":"407","author":"S. O. Krumke","year":"2008","unstructured":"Krumke, S. O., de Paepe, W. E., Rambau, J., & Stougie, L. (2008). Bincoloring. Theoretical Computer Science, 407(1\u20133), 231\u2013241.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"129_CR21","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1145\/3828.3833","volume":"32","author":"C. C. Lee","year":"1985","unstructured":"Lee, C. C., & Lee, D. T. (1985). A simple online bin packing algorithm. Journal of the ACM, 32(3), 562\u2013572.","journal-title":"Journal of the ACM"},{"key":"129_CR22","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/j.tcs.2003.05.006","volume":"321","author":"H. Shachnai","year":"2004","unstructured":"Shachnai, H., & Tamir, T. (2004). Tight bounds for online class-constrained packing. Theoretical Computer Science, 321, 103\u2013123.","journal-title":"Theoretical Computer Science"},{"issue":"1\u20133","key":"129_CR23","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1016\/j.tcs.2008.01.001","volume":"393","author":"E. C. Xavier","year":"2008","unstructured":"Xavier, E. C., & Miyazawa, F. K. (2008). The class constrained bin packing problem with applications to video-on-demand. Theoretical Computer Science, 393(1\u20133), 240\u2013259.","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"129_CR24","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1287\/opre.51.5.759.16753","volume":"51","author":"J. Yang","year":"2003","unstructured":"Yang, J., & Leung, J. Y.-T. (2003). The ordered open-end bin packing problem. Operations Research, 51(5), 759\u2013770.","journal-title":"Operations Research"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-009-0129-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-009-0129-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-009-0129-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,2]],"date-time":"2019-06-02T05:39:43Z","timestamp":1559453983000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-009-0129-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,12]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["129"],"URL":"https:\/\/doi.org\/10.1007\/s10951-009-0129-5","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9,12]]}}}