Apostol Natsev, Alexander Haubold, et al.
MMSP 2007
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.
Apostol Natsev, Alexander Haubold, et al.
MMSP 2007
Michael C. McCord, Violetta Cavalli-Sforza
ACL 2007
Alfonso P. Cardenas, Larry F. Bowman, et al.
ACM Annual Conference 1975
Fan Zhang, Junwei Cao, et al.
IEEE TETC