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 language | English |
|---|---|
| Pages (from-to) | 171-175 |
| Journal | Information Processing Letters |
| Volume | 63 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - 1997 |
Fingerprint Dive into the research topics of 'Shelf algorithms for on-line strip packing'. Together they form a unique fingerprint.
Cite this
Csirik, J., & Woeginger, G. J. (1997). Shelf algorithms for on-line strip packing. Information Processing Letters, 63(4), 171-175. https://doi.org/10.1016/S0020-0190(97)00120-8