A tale of two dimensional bin packing

N. Bansal, A. Lodi, M. Sviridenko

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

    21 Citations (Scopus)

    Abstract

    The 2-dimensional Bin Packing problem (2BP) is a generalization of the classical Bin Packing problem and is defined as follows: Given a collection of rectangles specified by their width and height, oack: these into minimum number of squares bins of units size. We study the case of "orthogonal packing without rotations", where rectangles cannot be rotated and must be packed parallel to the edges of a bin. Often in practical cases of 2BP problems there are additional constraints on how complicated the packing patterns in a bin can be. A well-studied and frequently used constraint is that every rectangle in the packing must be obtainable by recursively applying a sequence of edge-to-edge cuts parallel to the edge of the bin. Such cuts are known as guillotine cuts. Our main results is that the guillotine 2BP problem admits an asymptotic polynomial time approximation scheme. This is sharp contrast with the fact that the general 2BP problem is APX-Hard. En route to our main result, we show a structural theorem about approximating general guilootine packings by simpler packings, which could be of independent interest.
    Original languageEnglish
    Title of host publicationProceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005, Pittsburgh PA, USA, October 23-25, 2005)
    PublisherIEEE Computer Society
    Pages657-666
    ISBN (Print)0-7695-2468-0
    Publication statusPublished - 2005

    Fingerprint Dive into the research topics of 'A tale of two dimensional bin packing'. Together they form a unique fingerprint.

    Cite this