Bin packing in multiple dimensions: Inapproximability results and approximation schemes

• 成果类型: Article
• 署名作者: Bansal, N; Correa, JR; Kenyon, C; Sviridenko, M
• 署名单位: International Business Machines (IBM); IBM USA; Universidad Adolfo Ibanez; Brown University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1050.0168
• 发表日期: 2006
• 页码: 31-49
• 关键词: algorithm; square; bounds; time

摘要

We study the following packing problem: Given a collection of d-dimensional rectangles of specified sizes, pack them into the minimum number of unit cubes. We show that unlike the one-dimensional case, the two-dimensional packing problem cannot have an asymptotic polynomial time approximation scheme (APTAS), unless P = NP. On the positive side, we give an APTAS for the special case of packing d-dimensional cubes into the minimum number of unit cubes. Second, we give a polynomial time algorithm for packing arbitrary two-dimensional rectangles into at most OPT square bins with sides of length 1 + epsilon, where OPT denotes the minimum number of unit bins required to pack these rectangles. Interestingly, this result has no additive constant term, i.e., is not an asymptotic result. As a corollary, we obtain the first approximation scheme for the problem of placing a collection of rectangles in a minimum-area encasing rectangle.