LOWER BOUNDS FOR 1-DIMENSIONAL, 2-DIMENSIONAL AND 3-DIMENSIONAL ONLINE BIN PACKING ALGORITHMS

In this paper we discuss lower bounds for the asymptotic worst case ra tio of on-line algorithms for different kind of bin packing problems. Recently, Galambos and Frenk gave a simple proof of the 1.536... lower bound for the 1-dimensional bin packing problem. Following their idea s, we present a general technique that can be used to derive lower bou nds for other bin packing problems as well. We apply this technique to prove new lower bounds for the 2-dimensional (1.802...) and 3-dimensi onal (1.974...) bin packing problem.