1993-09-03
Two-dimensional rectangle packing: on-line methods and results
Publication
Publication
Discrete Applied Mathematics , Volume 45 - Issue 3 p. 197- 204
The first algorithms for the on-line two-dimensional rectangle packing problem were introduced by Coppersmith and Raghavan. They showed that for a family of heuristics 13/4 is an upper bound for the asymptotic worst-case ratios. We have investigated the Next Fit and the First Fit variants of their method. We proved that the asymptotic worst-case ratio equals 13/4 for the Next Fit variant and that 49/16 is an upper bound of the asymptotic worst-case ratio for the First Fit variant.
| Additional Metadata | |
|---|---|
| doi.org/10.1016/0166-218X(93)90009-D, hdl.handle.net/1765/11700 | |
| Discrete Applied Mathematics | |
| Organisation | Erasmus School of Economics |
|
Csirik, J., Frenk, H., & Labbé, M. (1993). Two-dimensional rectangle packing: on-line methods and results. Discrete Applied Mathematics, 45(3), 197–204. doi:10.1016/0166-218X(93)90009-D |
|
