{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T16:09:08Z","timestamp":1742918948038,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":15,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_495","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:04:13Z","timestamp":1461269053000},"page":"2319-2323","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Vector Bin Packing"],"prefix":"10.1007","author":[{"given":"David S.","family":"Johnson","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"495_CR221","doi-asserted-by":"publisher","first-page":"1256","DOI":"10.1137\/080736831","volume":"39","author":"N Bansal","year":"2009","unstructured":"Bansal N, Caprara A, Sviridenko M (2009) A new approximation method for set covering problems, with applications to multidimensional bin packing. SIAM J Comput 39:1256\u20131278","journal-title":"SIAM J Comput"},{"key":"495_CR222","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0166-218X(00)00267-5","volume":"111","author":"A Caprara","year":"2001","unstructured":"Caprara A, Toth P (2001) Lower bounds and algorithms for the 2-dimensional vector packing problem. Discret Appl Math 111:231\u2013262","journal-title":"Discret Appl Math"},{"key":"495_CR223","doi-asserted-by":"publisher","first-page":"837","DOI":"10.1137\/S0097539799356265","volume":"33","author":"C Chekuri","year":"2004","unstructured":"Chekuri C, Khanna S (2004) On multidimensional packing problems. SIAM J Comput 33:837\u2013851","journal-title":"SIAM J Comput"},{"key":"495_CR224","first-page":"361","volume":"9","author":"WF Csirik","year":"1990","unstructured":"Csirik WF, Frenk JBG, Labb\u00e9 M, Zhang S (1990) On the multidimensional vector packing. Acta Cybern 9:361\u2013369","journal-title":"Acta Cybern"},{"key":"495_CR225","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"J Vega de la","year":"1981","unstructured":"de la Vega J, Lueker GS (1981) Bin packing can be solved within 1 +\u03b5 in linear time. Combinatorica 1:349\u2013355","journal-title":"Combinatorica"},{"key":"495_CR226","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0097-3165(76)90001-7","volume":"21","author":"MR Garey","year":"1976","unstructured":"Garey MR, Graham RL, Johnson DS, Yao AC-C (1976) Resource constrained scheduling as generalized bin packing. J Comb Theory (A) 21:257\u2013298","journal-title":"J Comb Theory (A)"},{"key":"495_CR227","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson DS (1974) Approximation algorithms for combinatorial problems. J Comput Syst Sci 9:256\u2013278","journal-title":"J Comput Syst Sci"},{"key":"495_CR228","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1137\/0203025","volume":"3","author":"DS Johnson","year":"1974","unstructured":"Johnson DS, Demers A, Ullman JD, Garey MR, Graham RL (1974) Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J Comput 3:299\u2013325","journal-title":"SIAM J Comput"},{"key":"495_CR229","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1147\/rd.215.0443","volume":"21","author":"LT Kou","year":"1977","unstructured":"Kou LT, Markowski G (1977) Multidimensional bin packing algorithms. IBM J Res Dev 21:443\u2013448","journal-title":"IBM J Res Dev"},{"key":"495_CR2210","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/BF00999302","volume":"6","author":"K Maruyama","year":"1977","unstructured":"Maruyama K, Chang SK, Tang DT (1977) A general packing algorithm for multidimensional resource requirements. Int J Comput Inf Sci 6:131\u2013149","journal-title":"Int J Comput Inf Sci"},{"key":"495_CR2211","unstructured":"Panigrahy R, Talwar K, Uyeda L, Wieder U (2011) Heuristics for vector bin packing. Unpublished manuscript. (Available on the web)"},{"key":"495_CR2212","doi-asserted-by":"publisher","first-page":"962","DOI":"10.1016\/j.jpdc.2010.05.006","volume":"70","author":"M Stillwell","year":"2010","unstructured":"Stillwell M, Schanzenbach D, Vivien F, Casanova H (2010) Resource allocation algorithms for virtualized service hosting platforms. J Parallel Distrib Comput 70:962\u2013974","journal-title":"J Parallel Distrib Comput"},{"key":"495_CR2213","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/S0020-0190(97)00179-8","volume":"64","author":"GJ Woeginger","year":"1997","unstructured":"Woeginger GJ (1997) There is no asymptotic PTAS for two-dimensional vector packing. Inf Proc Lett 64:293\u2013297","journal-title":"Inf Proc Lett"},{"key":"495_CR2214","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1145\/322186.322187","volume":"27","author":"AC-C Yao","year":"1980","unstructured":"Yao AC-C (1980) New algorithms for bin packing. J ACM 27:207\u2013227","journal-title":"J ACM"},{"key":"495_CR2215","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman D (2007) Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput 3:103\u2013128","journal-title":"Theory Comput"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_495","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T15:33:36Z","timestamp":1553096016000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_495"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_495","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}