New lower bounds for certain classes of bin packing algorithms

On-line algorithms have been extensively studied for the one-dimensional bin packing problem. In this paper, we investigate two classes of one-dimensional bin packing algorithms, and we give better lower bounds for their asymptotic worst-case behavior. For on-line algorithms so far the best lower bound was given by van Vliet in (1992) [12], . 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 and we investigate the parametric case as well. For those lists where the elements are preprocessed according to their sizes in non-increasing order, Csirik et al. (1983) [1] proved that no on-line algorithm can have an asymptotic performance ratio smaller than . We improve this result to .