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 1/2 .
Caramia, M., Giordani, S. (2008). On the effectiveness of the harmonic shelf algorithm for on-line strip packing. DISCRETE MATHEMATICS, 308(16), 3699-3703 [10.1016/j.disc.2007.07.016].
On the effectiveness of the harmonic shelf algorithm for on-line strip packing
CARAMIA, MASSIMILIANO;GIORDANI, STEFANO
2008-01-01
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 1/2 .I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
