Two-dimensional bin packing with one-dimensional resource augmentation

N. Bansal, M. Sviridenko

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    7 Citaten (Scopus)
    1 Downloads (Pure)

    Samenvatting

    The two-dimensional bin packing problem 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, pack these into a minimum number of square bins of unit size. Recently, the problem was proved to be APX-hard even in the asymptotic case, i.e. when the optimum solutions require a large number of bins [N. Bansal, J. Correa, C. Kenyon, M. Sviridenko, Bin packing in multiple dimensions: Inapproximability results and approximation schemes, Math. Oper. Res. 31 (1) (2006) 31–49]. On the positive side, there exists a polynomial time algorithm that uses OPT bins whose sides have length (1+), where OPT denotes the number of unit sized bins used by the optimum solution [N. Bansal, J. Correa, C. Kenyon, M. Sviridenko, Bin packing in multiple dimensions: Inapproximability results and approximation schemes, Math. Oper. Res. 31 (1) (2006) 31–49]. A natural question that remains is the approximability of the problem when we are allowed to relax the size of the unit bins in only one dimension. In this paper, we show that there exists an asymptotic polynomial time approximation scheme for packing rectangles into bins of size 1×(1+).
    Originele taal-2Engels
    Pagina's (van-tot)143-153
    TijdschriftDiscrete Optimization
    Volume4
    Nummer van het tijdschrift2
    DOI's
    StatusGepubliceerd - 2007

    Vingerafdruk Duik in de onderzoeksthema's van 'Two-dimensional bin packing with one-dimensional resource augmentation'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit