A Lower Bound for On-Line One-Dimensional Bin Packing Algorithms

摘要

This paper is concerned with algorithms for which the pieces (numbers) in list L are available one at a time, and each piece must be placed in some bin before the next piece is available; such an algorithm is referred to as on-line. The performance measure used is the ratio of the number of bins used by an algorithm A in packing list L, A(L), to the optimum (minimum) number of bins required to pack the list, OPT(L).