Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
New Lower Bounds for Certain Classes of Bin Packing Algorithms
verfasst von : János Balogh, József Békési, Gábor Galambos
Erschienen in: Approximation and Online Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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}.$