In this paper we discuss lower bounds for the asymptotic worst case ratio 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 ideas, we present a general technique that can be used to derive lower bounds for other bin packing problems as well. We apply this technique to prove new lower bounds for the 2-dimensional (1.802...) and 3-dimensional (1.974...) bin packing problem.

, , , , ,,
Computing: archives for scientific computing
Erasmus School of Economics

Galambos, G., & van Vliet, A. (1994). Lower bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms. Computing: archives for scientific computing, 52(3), 281–297. doi:10.1007/BF02246509