{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:27:30Z","timestamp":1725460050350},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642380150"},{"type":"electronic","value":"9783642380167"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38016-7_12","type":"book-chapter","created":{"date-parts":[[2013,4,30]],"date-time":"2013-04-30T13:58:58Z","timestamp":1367330338000},"page":"131-144","source":"Crossref","is-referenced-by-count":5,"title":["Black and White Bin Packing"],"prefix":"10.1007","author":[{"given":"J\u00e1nos","family":"Balogh","sequence":"first","affiliation":[]},{"given":"J\u00f3zsef","family":"B\u00e9k\u00e9si","sequence":"additional","affiliation":[]},{"given":"Gyorgy","family":"Dosa","sequence":"additional","affiliation":[]},{"given":"Hans","family":"Kellerer","sequence":"additional","affiliation":[]},{"given":"Zsolt","family":"Tuza","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2012.04.017","volume":"440","author":"J. Balogh","year":"2012","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., Galambos, G.: New lower bounds for certain classes of bin packing algorithms. Theoretical Computer Science\u00a0440-441, 1\u201313 (2012)","journal-title":"Theoretical Computer Science"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Benko, A., Dosa, G., Tuza, Z.: Bin Covering with a general profit function: approximability results. Central European Journal of Operations Research (2012) (online published)","DOI":"10.1007\/s10100-012-0269-0"},{"issue":"8","key":"12_CR3","doi-asserted-by":"publisher","first-page":"1971","DOI":"10.1142\/S012905411100915X","volume":"22","author":"C. Bujtas","year":"2011","unstructured":"Bujtas, C., Dosa, G., Imreh, C., Nagy-Gy\u00f6rgy, J., Tuza, Z.: The Graph-Bin Packing Problem. Int. J. Found. Comput. Sci.\u00a022(8), 1971\u20131993 (2011)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"13-14","key":"12_CR4","doi-asserted-by":"publisher","first-page":"1914","DOI":"10.1016\/j.dam.2012.04.012","volume":"160","author":"J. Boyar","year":"2012","unstructured":"Boyar, J., Dosa, G., Epstein, L.: On the absolute approximation ratio for First Fit and related Results. Discrete Applied Mathematics\u00a0160(13-14), 1914\u20131923 (2012)","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR5","unstructured":"Coffman Jr, E., Garey, M., Johnson, D.: Approximation algorithms for bin packing: A survey. In: Approximation Algorithms for NP-hard Problems, pp. 46\u201393. PWS Publishing Co. (1996)"},{"key":"12_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-74450-4_1","volume-title":"Combinatorics, Algorithms, Probabilistic and Experimental Methodologies","author":"G. D\u00f3sa","year":"2007","unstructured":"D\u00f3sa, G.: The tight bound of first fit decreasing bin-packing algorithm is FFD(I) \u2264 11\/9OPT(I) + 6\/9. In: Chen, B., Paterson, M., Zhang, G. (eds.) ESCAPE 2007. LNCS, vol.\u00a04614, pp. 1\u201311. Springer, Heidelberg (2007)"},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"Dosa, G., Tuza, Z., Ye, D.: Bin packing with \u201cLargest In Bottom\u201d constraint: Tighter bounds and generalizations. Journal of Combinatorial Optimization (to appear), doi: 10.1007\/s10878-011-9408-0","DOI":"10.1007\/s10878-011-9408-0"},{"key":"12_CR8","unstructured":"Epstein, L.: Personal communication (2011)"},{"issue":"8","key":"12_CR9","doi-asserted-by":"publisher","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. Naval Research Logistics\u00a056(8), 780\u2013786 (2009)","journal-title":"Naval Research Logistics"},{"key":"12_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/11970125_13","volume-title":"Approximation and Online Algorithms","author":"L. Epstein","year":"2007","unstructured":"Epstein, L., Levin, A.: On bin packing with conflicts. In: Erlebach, T., Kaklamanis, C. (eds.) WAOA 2006. LNCS, vol.\u00a04368, pp. 160\u2013173. Springer, Heidelberg (2007)"},{"key":"12_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/978-3-540-74240-1_25","volume-title":"Fundamentals of Computation Theory","author":"L. Epstein","year":"2007","unstructured":"Epstein, L., Levin, A., van Stee, R.: Multi-dimensional packing with conflicts. In: Csuhaj-Varj\u00fa, E., \u00c9sik, Z. (eds.) FCT 2007. LNCS, vol.\u00a04639, pp. 288\u2013299. Springer, Heidelberg (2007)"},{"key":"12_CR12","volume-title":"Computer and Intractability: A Guide to the theory of NP-Completeness","author":"M.R. 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":"12_CR13","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n\n                  1\u2009\u2212\u2009\u03b5\n                  . Acta Mathematica\u00a0182, 105\u2013142 (1999)","journal-title":"Acta Mathematica"},{"key":"12_CR14","unstructured":"Johnson, D.S.: Near-optimal bin-packing algorithms, Doctoral Thesis, MIT, Cambridge (1973)"},{"issue":"4","key":"12_CR15","doi-asserted-by":"publisher","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. Journal of Combinatorial Optimization\u00a03(4), 363\u2013377 (1999)","journal-title":"Journal of Combinatorial Optimization"},{"key":"12_CR16","doi-asserted-by":"publisher","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. Information and Computation\u00a0132, 85\u2013108 (1997)","journal-title":"Information and Computation"},{"key":"12_CR17","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1137\/0203025","volume":"3","author":"D. Johnson","year":"1974","unstructured":"Johnson, D., Demers, A., Ullman, J., Garey, M., Graham, R.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing\u00a03, 299\u2013325 (1974)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR18","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 1982), pp. 312\u2013320 (1982)","DOI":"10.1109\/SFCS.1982.61"},{"key":"12_CR19","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1145\/3828.3833","volume":"32","author":"C.C. Lee","year":"1985","unstructured":"Lee, C.C., Lee, D.T.: A simple on-line packing algorithm. J. ACM\u00a032, 562\u2013572 (1985)","journal-title":"J. ACM"},{"key":"12_CR20","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W.F. Vega de la","year":"1981","unstructured":"de la Vega, W.F., Lueker, G.S.: Bin packing can be solved within 1\u2009+\u2009\u03b5 in linear time. Combinatorica\u00a01, 349\u2013355 (1981)","journal-title":"Combinatorica"},{"key":"12_CR21","first-page":"447","volume-title":"Topics in Industrial Mathematics","author":"P. Manyem","year":"2003","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":"12_CR22","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. Journal of Automata, Languages and Combinatorics\u00a08(4), 663\u2013674 (2003)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"12_CR23","unstructured":"McCloskey, B., Shankar, A.: Approaches to bin packing with clique-graph conflicts, Technical Report UCB\/CSD-05-1378, EECS Department, University of California, Berkeley (2005)"},{"issue":"5","key":"12_CR24","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1145\/585265.585269","volume":"49","author":"S. Seiden","year":"2002","unstructured":"Seiden, S.: On the online bin packing problem. Journal of the ACM (JACM)\u00a049(5), 640\u2013671 (2002)","journal-title":"Journal of the ACM (JACM)"},{"issue":"5","key":"12_CR25","doi-asserted-by":"publisher","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. Information Processing Letters\u00a043(5), 277\u2013284 (1992)","journal-title":"Information Processing Letters"},{"issue":"15","key":"12_CR26","doi-asserted-by":"publisher","first-page":"1668","DOI":"10.1016\/j.dam.2010.05.026","volume":"158","author":"B.Z. Xia","year":"2010","unstructured":"Xia, B.Z., Tan, Z.Y.: Tighter bounds of the First Fit algorithm for the bin-packing problem. Discrete Applied Mathematics\u00a0158(15), 1668\u20131675 (2010)","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR27","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D. Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of Max Clique and Chromatic Number. Theory of Computing\u00a03, 103\u2013128 (2007)","journal-title":"Theory of Computing"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38016-7_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T11:10:47Z","timestamp":1557659447000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38016-7_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642380150","9783642380167"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38016-7_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}