Shelf algorithms for on-line strip packing

✍ Scribed by János Csirik; Gerhard J. Woeginger

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 461 KB
• Volume: 63
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00120-8

✦ Synopsis

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 h, x 1.69 103. Moreover, we introduce and analyze another on-line shelf algorithm whose asymptotic worst case ratio comes arbitrarily close to h,. @ 1997 Elsevier Science B.V.