Shelf algorithms for on-line strip packing

J. Csirik, G.J. Woeginger

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    38 Citaten (Scopus)

    Samenvatting

    In the strip packing problem, the goal is to pack a set of rectangles into a vertical strip of unit width so as to minimize the total height of the strip needed. For the on-line version of this problem, Baker and Schwarz introduced the class of so-called shelf algorithms. One of these shelf algorithms, FFS, is the current champion for on-line strip packing. The asymptotic worst case ratio of FFS can be made arbitrarily close to 1.7. We show that no shelf algorithm for on-line strip packing can have an asymptotic worst case ratio better than h8 ˜ 1.69103. Moreover, we introduce and analyze another on-line shelf algorithm whose asymptotic worst case ratio comes arbitrarily close to h8.
    Originele taal-2Engels
    Pagina's (van-tot)171-175
    TijdschriftInformation Processing Letters
    Volume63
    Nummer van het tijdschrift4
    DOI's
    StatusGepubliceerd - 1997

    Vingerafdruk Duik in de onderzoeksthema's van 'Shelf algorithms for on-line strip packing'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit