A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
Authors:
- 1 November 2000
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 25 (4) , 645-656
Abstract
We present an asymptotic fully polynomial approximation scheme for strip-packing, or packing rectangles into a rectangle of fixed width and minimum height, a classical NP-hard cutting-stock problem. The algorithm, based on a new linear-programming relaxation, finds a packing of n rectangles whose total height is within a factor of (1 + ε) of optimal (up to an additive term), and has running time polynomial both in n and in 1/ε.Keywords
This publication has 15 references indexed in Scilit:
- A Strip-Packing Algorithm with Absolute Performance Bound 2SIAM Journal on Computing, 1997
- Rangements optimaux de carrés unité dans une bande infinieAnnales de la Faculté des sciences de Toulouse : Mathématiques, 1997
- Fast Approximation Algorithms for Fractional Packing and Covering ProblemsMathematics of Operations Research, 1995
- A 54 algorithm for two-dimensional packingJournal of Algorithms, 1981
- Bin packing can be solved within 1 + ε in linear timeCombinatorica, 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
- On packing squares with equal squaresJournal of Combinatorial Theory, Series A, 1975