Bin packing in multiple dimensions : inapproximability results and approximation schemes

N. Bansal, J.R. Correa, C. Kenyon, M. Sviridenko

    Research output: Contribution to journalArticleAcademicpeer-review

    84 Citations (Scopus)

    Abstract

    We study the following packing problem: Given a collection of d-dimensional rectangles of specified sizes, pack them into the minimum number of unit cubes. We show that unlike the one-dimensional case, the two-dimensional packing problem cannot have an asymptotic polynomial time approximation scheme (APTAS), unless P = NP. On the positive side, we give an APTAS for the special case of packing d-dimensional cubes into the minimum number of unit cubes. Second, we give a polynomial time algorithm for packing arbitrary two-dimensional rectangles into at most OPT square bins with sides of length 1 + epsilon, where OPT denotes the minimum number of unit bins required to pack these rectangles. Interestingly, this result has no additive constant term, i.e., is not an asymptotic result. As a corollary, we obtain the first approximation scheme for the problem of placing a collection of rectangles in a minimum-area encasing rectangle.
    Original languageEnglish
    Pages (from-to)31-49
    JournalMathematics of Operations Research
    Volume31
    Issue number1
    DOIs
    Publication statusPublished - 2006

    Fingerprint Dive into the research topics of 'Bin packing in multiple dimensions : inapproximability results and approximation schemes'. Together they form a unique fingerprint.

    Cite this