Advertisement
Published in:
2011 | OriginalPaper | Chapter
New Lower Bounds for Certain Classes of Bin Packing Algorithms
Authors : János Balogh, József Békési, Gábor Galambos
Published in: Approximation and Online Algorithms
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
On-line algorithms have been extensively studied for the one-dimensional bin packing problem. In this paper we investigate two classes of the one- dimensional bin packing algorithms, and we give lower bounds for their asymptotic worst-case behaviour. For on-line algorithms so far the best lower bound was given by van Vliet in 1992 [13]. He proved that there is no on-line bin packing algorithm with better asymptotic performance ratio than 1.54014.... In this paper we give an improvement on this bound to
$\frac{248}{161}= 1.54037\ldots$
and we investigate the parametric case as well. For those lists where the elements are preprocessed according to their sizes in decreasing order Csirik et al. [1] proved that no on-line algorithm can have an asymptotic performance ratio smaller than
$\frac{8}{7}$
. We improve this result to
$\frac{54}{47}.$