Shelf algorithms for on-line strip packing

J. Csirik, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    38 Citations (Scopus)

    Abstract

    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.
    Original languageEnglish
    Pages (from-to)171-175
    JournalInformation Processing Letters
    Volume63
    Issue number4
    DOIs
    Publication statusPublished - 1997

    Fingerprint Dive into the research topics of 'Shelf algorithms for on-line strip packing'. Together they form a unique fingerprint.

  • Cite this