# ICS 269, Spring 2005: Theory Seminar

## 20 May 2005:

John Augustine

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+e) of
optimal (up to an additive term), and has running time polynomial both
in n and in 1/e.

Paper: Claire Kenyon and Eric Remila, "A Near-Optimal Solution to a
Two-Dimensional Cutting Stock Problem," Mathematics of Operations
Research, Volume 25 , Issue 4 (November 2000).