New approximability and inapproximability results for 2-dimensional bin packing

N. Bansal, M. Sviridenko

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    1 Downloads (Pure)

    Samenvatting

    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.
    Originele taal-2Engels
    TitelProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04, New Orleans LA, USA, January 11-14, 2004)
    RedacteurenJ.I. Munro
    Plaats van productieNew York
    UitgeverijAssociation for Computing Machinery, Inc
    Pagina's196-203
    ISBN van geprinte versie0-89871-558-X
    StatusGepubliceerd - 2004

    Vingerafdruk

    Duik in de onderzoeksthema's van 'New approximability and inapproximability results for 2-dimensional bin packing'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit