Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
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 + ε, 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. © 2006 INFORMS.
Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
Alessandro Morari, Roberto Gioiosa, et al.
IPDPS 2011
Nanda Kambhatla
ACL 2004
Alfonso P. Cardenas, Larry F. Bowman, et al.
ACM Annual Conference 1975