A Strip-Packing Algorithm with Absolute Performance Bound 2
Author:
- A. SteinbergASA. Steinberg
- 1 March 1997
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 26 (2) , 401-409
Abstract
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.
Keywords
This publication has 7 references indexed in Scilit:
- Multidimensional on-line bin packing: Algorithms and worst-case analysisOperations Research Letters, 1989
- Approximation Algorithms for Bin-Packing — An Updated Survey1984
- A 54 algorithm for two-dimensional packingJournal of Algorithms, 1981
- Performance Bounds for Orthogonal Oriented Two-Dimensional Packing AlgorithmsSIAM Journal on Computing, 1981
- Orthogonal Packings in Two DimensionsSIAM Journal on Computing, 1980
- Performance Bounds for Level-Oriented Two-Dimensional Packing AlgorithmsSIAM Journal on Computing, 1980
- A 2.5 times optimal algorithm for packing in two dimensionsInformation Processing Letters, 1980