1987-09-01
Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem
Publication
Publication
Computing: archives for scientific computing , Volume 39 - Issue 3 p. 201- 217
We present a new approximation algorithm for the two-dimensional bin-packing problem. The algorithm is based on two one-dimensional bin-packing algorithms. Since the algorithm is of next-fit type it can also be used for those cases where the output is required to be on-line (e. g. if we open an new bin we have no possibility to pack elements into the earlier opened bins). We give a tight bound for its worst-case and show that this bound is a parameter of the maximal sizes of the items to be packed. Moreover, we also present a probabilistic analysis of this algorithm.
| Additional Metadata | |
|---|---|
| , , , , , | |
| doi.org/10.1007/BF02309555, hdl.handle.net/1765/11691 | |
| Computing: archives for scientific computing | |
| Organisation | Erasmus School of Economics |
|
Frenk, H., & Galambos, G. (1987). Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem. Computing: archives for scientific computing, 39(3), 201–217. doi:10.1007/BF02309555 |
|
