{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:31:07Z","timestamp":1759847467791},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,3,18]],"date-time":"2014-03-18T00:00:00Z","timestamp":1395100800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2015,1]]},"DOI":"10.1007\/s00224-014-9538-8","type":"journal-article","created":{"date-parts":[[2014,3,18]],"date-time":"2014-03-18T03:31:46Z","timestamp":1395113506000},"page":"137-155","source":"Crossref","is-referenced-by-count":13,"title":["Online Results for Black and White Bin Packing"],"prefix":"10.1007","volume":"56","author":[{"given":"J\u00e1nos","family":"Balogh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00f3zsef","family":"B\u00e9k\u00e9si","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gy\u00f6rgy","family":"D\u00f3sa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leah","family":"Epstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hans","family":"Kellerer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zsolt","family":"Tuza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,3,18]]},"reference":[{"key":"9538_CR1","doi-asserted-by":"crossref","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., D\u00f3sa, Gy., Kellerer H, Tuza, Zs.: Black and white bin packing. In: Proceedings of WAOA\u201912, Lecture Notes in Computer Science, vol. 7846, pp. 131\u2013144 (2013)","DOI":"10.1007\/978-3-642-38016-7_12"},{"key":"9538_CR2","doi-asserted-by":"crossref","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., Galambos, G.: New lower bounds for certain classes of bin packing algorithms. Theor. Comput. Sci. 440\u2013441, 1\u201313 (2012)","DOI":"10.1016\/j.tcs.2012.04.017"},{"issue":"4","key":"9538_CR3","doi-asserted-by":"crossref","first-page":"805","DOI":"10.1007\/s10100-012-0269-0","volume":"21","author":"A Benko\u030b","year":"2013","unstructured":"Benko\u030b, A., D\u00f3sa, Gy., Tuza, Zs.: Bin covering with a general profit function: approximability results. CEJOR 21(4), 805\u2013816 (2013)","journal-title":"CEJOR"},{"issue":"13\u201314","key":"9538_CR4","doi-asserted-by":"crossref","first-page":"1914","DOI":"10.1016\/j.dam.2012.04.012","volume":"160","author":"J Boyar","year":"2012","unstructured":"Boyar, J., D\u00f3sa, Gy., Epstein, L.: On the absolute approximation ratio for first fit and related results. Discret. Appl. Math. 160(13\u201314), 1914\u20131923 (2012)","journal-title":"Discret. Appl. Math."},{"key":"9538_CR5","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes \u2013 A Survey. SIAM Monographs on Discrete Mathematics and Applications","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes \u2013 A Survey. SIAM Monographs on Discrete Mathematics and Applications. SIAM Press, Philadelphia (1999)"},{"key":"9538_CR6","unstructured":"Coffman, E.G. Jr., Garey, M., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-hard Problems, pp. 46\u201393. PWS Publishing Co., Boston (1996)"},{"key":"9538_CR7","doi-asserted-by":"crossref","unstructured":"Csirik, J., Woeginger, G.J.: On-line packing and covering problems. In: Fiat A., Woeginger G. J. (eds.) Online Algorithms: The State of the Art, pp. 147\u2013177 (1998)","DOI":"10.1007\/BFb0029568"},{"key":"9538_CR8","unstructured":"D\u00f3sa, Gy., Sgall, J.: First fit bin packing: a tight analysis. In: Proceedings of STACS 2013, LIPIcs, vol. 20, pp. 538\u2013549 (2013)"},{"issue":"3","key":"9538_CR9","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1007\/s10878-011-9408-0","volume":"26","author":"Gy D\u00f3sa","year":"2013","unstructured":"D\u00f3sa, Gy., Tuza, Zs., Ye, D.: Bin packing with \u201cLargest In Bottom\u201d constraint: tighter bounds and generalizations. J. Comb. Optim. 26(3), 416\u2013436 (2013)","journal-title":"J. Comb. Optim."},{"issue":"8","key":"9538_CR10","doi-asserted-by":"crossref","first-page":"780","DOI":"10.1002\/nav.20383","volume":"56","author":"L Epstein","year":"2009","unstructured":"Epstein, L.: On online bin packing with LIB constraints. Nav. Res. Logist. 56(8), 780\u2013786 (2009)","journal-title":"Nav. Res. Logist."},{"issue":"3","key":"9538_CR11","doi-asserted-by":"crossref","first-page":"1270","DOI":"10.1137\/060666329","volume":"19","author":"L Epstein","year":"2008","unstructured":"Epstein, L., Levin, A.: On bin packing with conflicts. SIAM J. Optim. 19(3), 1270\u20131298 (2008)","journal-title":"SIAM J. Optim."},{"key":"9538_CR12","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W Fernandez de la Vega","year":"1981","unstructured":"Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within 1+\u03b5 in linear time. Combinatorica 1, 349\u2013355 (1981)","journal-title":"Combinatorica"},{"key":"9538_CR13","volume-title":"Computer and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computer and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"9538_CR14","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn.Elsevier, Amsterdam (2004)","DOI":"10.1016\/S0167-5060(04)80059-1"},{"issue":"4","key":"9538_CR15","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1023\/A:1009871302966","volume":"3","author":"K Jansen","year":"1999","unstructured":"Jansen, K.: An approximation scheme for bin packing with conflicts. J. Comb. Optim. 3(4), 363\u2013377 (1999)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"9538_CR16","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1006\/inco.1996.2616","volume":"132","author":"K Jansen","year":"1997","unstructured":"Jansen, K., \u00d6hring, S.: Approximation algorithms for time constrained scheduling. Inf. Comput. 132(2), 85\u2013108 (1997)","journal-title":"Inf. Comput."},{"key":"9538_CR17","volume-title":"Near-Optimal Bin-Packing Algorithms. Doctoral Thesis","author":"DS Johnson","year":"1973","unstructured":"Johnson, D.S.: Near-Optimal Bin-Packing Algorithms. Doctoral Thesis. MIT, Cambridge (1973)"},{"issue":"3","key":"9538_CR18","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1016\/S0022-0000(74)80026-7","volume":"8","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Fast algorithms for bin packing. J. Comput. Syst. Sci. 8(3), 272\u2013314 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"9538_CR19","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1137\/0203025","volume":"3","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S., Demers, A., Ullman, J., Garey, M., Graham, R.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3, 25\u2013278 (1974)","journal-title":"SIAM J. Comput."},{"key":"9538_CR20","doi-asserted-by":"crossref","unstructured":"Karmarkar, N., Karp, R.: An efficient approximation scheme for the one-dimensional bin packing problem. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS\u201982), pp. 312\u2013320 (1982)","DOI":"10.1109\/SFCS.1982.61"},{"key":"9538_CR21","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1145\/3828.3833","volume":"32","author":"CC Lee","year":"1985","unstructured":"Lee, C.C., Lee, D.T.: A simple on-line packing algorithm. J. ACM 32, 562\u2013572 (1985)","journal-title":"J. ACM"},{"key":"9538_CR22","unstructured":"Manyem, P.: Uniform sized bin packing and covering: online version. In: Misra, J.C. (ed.) Topics in Industrial Mathematics, pp. 447\u2013485. Narosa Publishing House, New Delhi (2003)"},{"issue":"4","key":"9538_CR23","first-page":"663","volume":"8","author":"P Manyem","year":"2003","unstructured":"Manyem, P., Salt, R., Visser, M.: Approximation lower bounds in online LIB bin packing and covering. J. Autom. Lang. Comb. 8(4), 663\u2013674 (2003)","journal-title":"J. Autom. Lang. Comb."},{"issue":"5","key":"9538_CR24","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1145\/585265.585269","volume":"49","author":"S Seiden","year":"2002","unstructured":"Seiden, S.: On the online bin packing problem. J. ACM 49(5), 640\u2013671 (2002)","journal-title":"J. ACM"},{"issue":"4","key":"9538_CR25","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1002\/1520-6750(199406)41:4<579::AID-NAV3220410409>3.0.CO;2-G","volume":"41","author":"D Simchi-Levi","year":"1994","unstructured":"Simchi-Levi, D.: New worst-case results for the bin-packing problem. Nav. Res. Logist. 41(4), 579\u2013585 (1994)","journal-title":"Nav. Res. Logist."},{"key":"9538_CR26","unstructured":"Ullman, J.D.: The Performance of a Memory Allocation Algorithm. Technical Report 100, Princeton University, Princeton 695 (1971)"},{"issue":"5","key":"9538_CR27","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0020-0190(92)90223-I","volume":"43","author":"A Vliet van","year":"1992","unstructured":"van Vliet, A.: An improved lower bound for on-line bin packing algorithms. Inf. Process. Lett. 43(5), 277\u2013284 (1992)","journal-title":"Inf. Process. Lett."},{"issue":"15","key":"9538_CR28","doi-asserted-by":"crossref","first-page":"1668","DOI":"10.1016\/j.dam.2010.05.026","volume":"158","author":"BZ Xia","year":"2010","unstructured":"Xia, B.Z., Tan, Z.Y.: Tighter bounds of the First Fit algorithm for the bin-packing problem. Discret. Appl. Math. 158(15), 1668\u20131675 (2010)","journal-title":"Discret. Appl. Math."},{"key":"9538_CR29","doi-asserted-by":"crossref","unstructured":"Yao, A.: Probabilistic computations: toward a unified measure of complexity (extended abstract). In: Proceedings of the 18th Annual Symposium on Foundations of Computer Science (FOCS\u201977), pp. 222\u2013227 (1977)","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9538-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9538-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9538-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,8]],"date-time":"2019-08-08T14:54:46Z","timestamp":1565276086000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9538-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,3,18]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["9538"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9538-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,3,18]]}}}