Does randomization help in on-line bin packing? (Q1198004): Difference between revisions

In bin packing problems, a list of items is to be packed into a minimum number of bins of uniform size. We consider the class of on-line algorithms in which we are given the items sequentially and we must pack the current item before we see subsequent items. Lower bounds have been proved for deterministic algorithms for different bin packing problems. In this note we show that the same lower bounds hold for randomized algorithms.