| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4648763 | Discrete Mathematics | 2008 | 5 Pages |
Abstract
In [J. Csirik, G.J. Woeginger, An on-line algorithm for multidimensional bin packing, Inform. Process. Lett. 63 (1997) 171–175] the authors study the asymptotic worst case ratio between the height of the strip needed to on-line pack a list of boxes by means of the Harmonic Shelf Algorithm and the height of the strip used by an optimal algorithm. In this note we analyze the effectiveness of the former algorithm in terms of the ratio between the unused area inside the strip and the total size of this strip, and we show that the Harmonic Shelf Algorithm is also capable of packing items so that the asymptotic worst case value of this ratio comes arbitrarily close to 12.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Massimiliano Caramia, Stefano Giordani,