Approximate Strip Packing

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+/spl epsiv/) of optimal, and has running time polynomial both in n and in 1//spl epsiv/. It is based on a reduction to fractional bin-packing, and can be performed by 5 stages of guillotine cuts.

Authors

• Claire Mathieu
• Eric Rémila

Keywords

• Strips
• Polynomials
• Application software
• Computer science
• Processor scheduling
• Algorithm design and analysis
• Integer linear programming
• Strip Packing
• Running Time
• Total Height
• Minimum Height
• Heuristic
• Linear Programming
• Estimation Strategy
• End Of Step
• Partial Order
• Strip Width
• Piece Of Wood
• Fractional Problem
• Idea Of This Paper
• Linear Programming Approach
• Competitive Ratio