Summary: 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 A. van Vliet in [Inf. Process. Lett. 43, No. 5, 277–284 (1992; Zbl 0764.68083)]. He proved that there is no on-line bin packing algorithm with better asymptotic performance ratio than \(1.54014\dots \). 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. 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}\).
For the entire collection see [Zbl 1206.68011].