New approximability and inapproximability results for 2-dimensional bin packing

N. Bansal, M. Sviridenko

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    1 Downloads (Pure)


    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.
    Original languageEnglish
    Title of host publicationProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04, New Orleans LA, USA, January 11-14, 2004)
    EditorsJ.I. Munro
    Place of PublicationNew York
    PublisherAssociation for Computing Machinery, Inc
    ISBN (Print)0-89871-558-X
    Publication statusPublished - 2004


    Dive into the research topics of 'New approximability and inapproximability results for 2-dimensional bin packing'. Together they form a unique fingerprint.

    Cite this