DocumentCode
2641718
Title
Approximate strip packing
Author
Kenyon, Claire ; Rémila, Eric
Author_Institution
LIP, Ecole Normale Superieure de Lyon, France
fYear
1996
fDate
14-16 Oct 1996
Firstpage
31
Lastpage
36
Abstract
We present an 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 finds a packing of n rectangles whose total height is within a factor of (1+ε) of optimal, and has running time polynomial both in n and in 1/ε. It is based on a reduction to fractional bin-packing, and can be performed by 5 stages of guillotine cuts
Keywords
computational complexity; computational geometry; operations research; NP-hard cutting-stock problem; fractional bin-packing; guillotine cuts; packing rectangles; strip-packing; Algorithm design and analysis; Application software; Computer science; Integer linear programming; Polynomials; Processor scheduling; Strips;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on
Conference_Location
Burlington, VT
ISSN
0272-5428
Print_ISBN
0-8186-7594-2
Type
conf
DOI
10.1109/SFCS.1996.548461
Filename
548461
Link To Document