Two-dimensional rectangle packing: on-line methods and results
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.
|Discrete Applied Mathematics|
|Organisation||Erasmus School of Economics|
Csirik, J, Frenk, J.B.G, & 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