1994-09-01
Lower bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms
Publication
Publication
Computing: archives for scientific computing , Volume 52 - Issue 3 p. 281- 297
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.
| Additional Metadata | |
|---|---|
| , , , , , | |
| doi.org/10.1007/BF02246509, hdl.handle.net/1765/71894 | |
| Computing: archives for scientific computing | |
| Organisation | 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 |
|
