Abstract. We study the multidimensional generalization of the classical Bin Packing problem: Given a collection of d-dimensional rectangles of specified sizes, the goal is to pack them into the minimum number of unit cubes. A long history of results exists for this problem and its special cases. Currently, the best known approximation algorithm for packing two-dimensional rectangles achieves a guarantee of 1.69 in the asymptotic case (i.e., when the optimum uses a large number of bins) [3] . An important open question has been whether 2−dimensional bin packing is essentially similar to the 1−dimensional case in that it admits an asymptotic polynomial time approximation scheme (APTAS) [12, 17] or not. We answer the question in the negative and show that the problem is APX hard in the asymptotic sense. On the positive side, we give the following results: First, we consider the special case where we have to pack d-dimensional cubes into the minimum number of unit cubes. We give an asymptotic polynomial time approximation scheme for this problem. This represents a significant improvement over the previous best known asymptotic approximation factor of 2 − (2/3) , and settles the approximability of the problem. Second, we give a polynomial time algorithm for packing arbitrary 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 does not have an additive constant term i.e., is not an asymptotic result. As a corollary, we obtain a polynomial time approximation scheme for the problem of placing a collection of rectangles in a minimum area encasing rectangle, settling also the approximability of this problem.
Bansal et al. REF showed that there is no asymptotic approximation scheme for the rectangle bin packing problem, which implies that there is no APTAS for the 3-dimensional strip packing problem.
Bin packing in multiple dimensions: Inapproximability results and approximation schemes
MATHEMATICS OF OPERATIONS RESEARCH
Mathematics Computer Science