{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T16:29:23Z","timestamp":1772296163767,"version":"3.50.1"},"reference-count":31,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[2001,8,1]],"date-time":"2001-08-01T00:00:00Z","timestamp":996624000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4368,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2001,8]]},"DOI":"10.1016\/s0166-218x(00)00267-5","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T14:23:14Z","timestamp":1027606994000},"page":"231-262","source":"Crossref","is-referenced-by-count":84,"title":["Lower bounds and algorithms for the 2-dimensional vector packing problem"],"prefix":"10.1016","volume":"111","author":[{"given":"Alberto","family":"Caprara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paolo","family":"Toth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(00)00267-5_BIB1","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1287\/opre.46.3.316","article-title":"Branch-and-price: column generation for solving huge integer programs","volume":"46","author":"Barnhart","year":"1998","journal-title":"Oper. Res."},{"key":"10.1016\/S0166-218X(00)00267-5_BIB2","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/S0166-218X(98)00046-8","article-title":"Properties of some ILP formulations of a class of partitioning problems","volume":"87","author":"Caprara","year":"1998","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(00)00267-5_BIB3","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/BF02680559","article-title":"Worst-case analyses, linear programming and the bin packing problem","volume":"83","author":"Chan","year":"1998","journal-title":"Math. Programming"},{"key":"10.1016\/S0166-218X(00)00267-5_BIB4","unstructured":"C. Chekuri, S. Khanna, On multi-dimensional packing problems, Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999), ACM Press, New York, 1999."},{"key":"10.1016\/S0166-218X(00)00267-5_BIB5","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0166-218X(96)80459-8","article-title":"An improved lower bound for the bin packing problem","volume":"66","author":"Chen","year":"1996","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(00)00267-5_BIB6","unstructured":"E.G. Coffman Jr., M.R. Garey, D.S. Johnson, Approximation algorithms for bin-packing \u2014 an updated survey, in: D.S. Hochbaum (Ed.), Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, Boston, 1997."},{"key":"10.1016\/S0166-218X(00)00267-5_BIB7","series-title":"Introduction to Algorithms","author":"Cormen","year":"1990"},{"key":"10.1016\/S0166-218X(00)00267-5_BIB8","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF02288324","article-title":"Solving non-bipartite matching problems via shortest path techniques","volume":"13","author":"Derigs","year":"1988","journal-title":"Ann. Oper. Res."},{"key":"10.1016\/S0166-218X(00)00267-5_BIB9","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1287\/mnsc.17.5.259","article-title":"The loading problem","volume":"17","author":"Eilon","year":"1971","journal-title":"Management Sci."},{"key":"10.1016\/S0166-218X(00)00267-5_BIB10","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/BF00226291","article-title":"A hybrid grouping genetic algorithm for bin packing","volume":"2","author":"Falkenauer","year":"1996","journal-title":"J. Heuristics"},{"key":"10.1016\/S0166-218X(00)00267-5_BIB11","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02579456","article-title":"Bin-packing can be solved within 1+\u03b5 in linear time","volume":"1","author":"Fernandez de la Vega","year":"1981","journal-title":"Combinatorica"},{"key":"10.1016\/S0166-218X(00)00267-5_BIB12","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0097-3165(76)90001-7","article-title":"Resource constrained scheduling as generalized bin packing","volume":"21","author":"Garey","year":"1976","journal-title":"J. Combin. Theory (A)"},{"key":"10.1016\/S0166-218X(00)00267-5_BIB13","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S0166-218X(00)00267-5_BIB14","unstructured":"A.M.H. Gerards, Matching, in: M.O. Ball, T.L. Magnanti, C.L. Monma, G.L. Nemhauser (Eds.), Handbook in Operations Research and Management Sciences, Vol.: Networks, North-Holland, Amsterdam, 1995."},{"key":"10.1016\/S0166-218X(00)00267-5_BIB15","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1287\/opre.9.6.849","article-title":"A linear programming approach to the cutting stock problem","volume":"9","author":"Gilmore","year":"1961","journal-title":"Oper. Res."},{"key":"10.1016\/S0166-218X(00)00267-5_BIB16","doi-asserted-by":"crossref","first-page":"863","DOI":"10.1287\/opre.11.6.863","article-title":"A linear programming approach to the cutting stock problem: Part II","volume":"11","author":"Gilmore","year":"1963","journal-title":"Oper. Res."},{"key":"10.1016\/S0166-218X(00)00267-5_BIB17","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","article-title":"The ellipsoid algorithm and its consequences in combinatorial optimization","volume":"1","author":"Gr\u00f6tschel","year":"1981","journal-title":"Combinatorica"},{"key":"10.1016\/S0166-218X(00)00267-5_BIB18","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1137\/0606049","article-title":"Bithreshold graphs","volume":"6","author":"Hammer","year":"1985","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"10.1016\/S0166-218X(00)00267-5_BIB19","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BF02085642","article-title":"Multiple-type, two-dimensional bin packing problems: applications and algorithms","volume":"50","author":"Han","year":"1994","journal-title":"Ann. Oper. Res."},{"key":"10.1016\/S0166-218X(00)00267-5_BIB20","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/nav.3800250209","article-title":"An algorithm for a class of loading problems","volume":"25","author":"Hung","year":"1978","journal-title":"Naval Res. Logistics Quart."},{"key":"10.1016\/S0166-218X(00)00267-5_BIB21","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0166-218X(90)90094-S","article-title":"Lower bounds and reduction procedures for the bin packing problem","volume":"28","author":"Martello","year":"1990","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(00)00267-5_BIB22","series-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"Martello","year":"1990"},{"key":"10.1016\/S0166-218X(00)00267-5_BIB23","unstructured":"S. Martello, P. Toth, Upper bounds and algorithms for the two-constraint knapsack problem, Working paper, University of Bologna, 1996."},{"key":"10.1016\/S0166-218X(00)00267-5_BIB24","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF00999302","article-title":"A general packing algorithm for multidimensional resource requirements","volume":"6","author":"Maruyama","year":"1977","journal-title":"Internat. J. Comput. Inform. Sci."},{"key":"10.1016\/S0166-218X(00)00267-5_BIB25","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0305-0548(94)90059-0","article-title":"A branch-and-bound algorithm for the two-dimensional vector packing problem","volume":"21","author":"Spieksma","year":"1994","journal-title":"Comput. oper. Res."},{"key":"10.1016\/S0166-218X(00)00267-5_BIB26","doi-asserted-by":"crossref","unstructured":"J.M. Valerio de Carvalho, Exact solution of cutting stock problems using column generation and branch-and-bound, International Transactions in Operational Research 5 (1998) 35\u201344.","DOI":"10.1111\/j.1475-3995.1998.tb00100.x"},{"key":"10.1016\/S0166-218X(00)00267-5_BIB27","doi-asserted-by":"crossref","unstructured":"P.H. Vance, Branch-and-price algorithms for the one-dimensional cutting stock problem, Comput. Optim. Appl. 9 (1998) 211\u2013228.","DOI":"10.1023\/A:1018346107246"},{"key":"10.1016\/S0166-218X(00)00267-5_BIB28","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01300970","article-title":"Solving binary cutting stock problems by column generation and branch-and-bound","volume":"3","author":"Vance","year":"1994","journal-title":"Comput. Optim. Appl."},{"key":"10.1016\/S0166-218X(00)00267-5_BIB29","doi-asserted-by":"crossref","unstructured":"F. Vanderbeck, Computational study of a column generation algorithm for bin packing and cutting stock problems, Math. Programming 86 (1999) 565\u2013594","DOI":"10.1007\/s101070050105"},{"key":"10.1016\/S0166-218X(00)00267-5_BIB30","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/S0020-0190(97)00179-8","article-title":"There is no asymptotic PTAS for two-dimensional vector packing","volume":"64","author":"Woeginger","year":"1997","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0166-218X(00)00267-5_BIB31","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1145\/322186.322187","article-title":"New algorithms for bin packing","volume":"27","author":"Yao","year":"1980","journal-title":"J. ACM"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X00002675?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X00002675?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,23]],"date-time":"2019-04-23T17:55:35Z","timestamp":1556042135000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X00002675"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,8]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2001,8]]}},"alternative-id":["S0166218X00002675"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(00)00267-5","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2001,8]]}}}