Journal
MATHEMATICS OF OPERATIONS RESEARCH
Volume 25, Issue 4, Pages 645-656Publisher
INST OPERATIONS RESEARCH MANAGEMENT SCIENCES
DOI: 10.1287/moor.25.4.645.12118
Keywords
cutting-stock; strip-packing; fully polynomial approximation scheme
Ask authors/readers for more resources
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 + epsilon) of optimal (up to an additive term), and has running time polynomial both in n and in 1/epsilon.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available