New approximability and inapproximability results for 2-dimensional bin packing

We study the 2-dimensional generalization of the classical Bin Packing problem: Given a collection of rectangles of specified size (width, height), the goal is to pack these into minimum number of square bins of unit size. A long history of results exists for this problem and its special cases [3, 14, 10, 18, 9, 1, 15]. Currently, the best known approximation algorithm achieves a guarantee of 1.69 in the asymptotic case (i.e. when the optimum uses a large number of bins) [1]. However, 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) [8, 13] or not? We answer the question in the negative and show that the problem is APX hard in the asymptotic case. On the other hand, we give an asymptotic PTAS for the special case when all the rectangles to be packed are squares (or more generally hypercubes). This improves upon the previous best known guarantee of 1.454 for d = 2 [9] and 2 - (2/3)d for d > 2 [15], and settles the approximability for this special case.