Two-dimensional rectangle packing: on-line methods and results
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.
|Persistent URL||dx.doi.org/10.1016/0166-218X(93)90009-D, hdl.handle.net/1765/11700|
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