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. 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). 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) 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 and 2-(2/3)d for d>2 and settles the approximability for this special case.
By: Nikhil Bansal, Maxim Sviridenko
Published in: RC22900 in 2003
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .