SIAM Journal on Computing · 1997 · 194 citations · 6 references
ComputingComputer ScienceAlgorithmsComputational GeometryOptimizationApproximation AlgorithmsCombinatorial OptimizationGeometric PackingPacking Problems
This paper proposes a new approximation algorithm M for packing rectangles into a strip with unit width and unbounded height so as to minimize the total height of the packing. It is shown that for any list L of rectangles, $M(L) \leq 2\cdot \mbox{OPT}(L)$, where $M(L)$ is the strip height actually used by the algorithm M when applied to L and OPT$(L)$ is the minimum possible height within which the rectangles in L can be packed.
6
Orthogonal Packings in Two Dimensions
Brenda S. Baker, E. G. Coffman, Ronald L. Rivest · SIAM Journal on Computing · 1980 · 695 citations
Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
E. G. Coffman, M. R. Garey, David S. Johnson et al. · SIAM Journal on Computing · 1980 · 478 citations
A algorithm for two-dimensional packing
Brenda S. Baker, Donna J. Brown, Howard P. Katseff · Journal of Algorithms · 1981 · 154 citations