IMADA - Department of Mathematics and Computer Science |
The strip packing problem is to pack a set of rectangles into a strip of fixed width and minimum length. In this talk we present asymptotic polynomial time approximation schemes for this problem without and with 90o rotations. The additive constant in the approximation ratios of both algorithms is 1, improving on the additive term in the approximation ratios of the algorithm by Kenyon and Rémila (for the problem without rotations) and Jansen and van Stee (for the problem with rotations), both of which have a larger additive constant O(1/ε2), ε > 0. The algorithms were derived from the study of the rectangle packing problem: Given a set R of rectangles with positive profits, the goal is to find and pack a maximum profit subset of R into a unit size square bin [0,1] × [0,1]. We present algorithms that for any value ε > 0 find a subset R' ⊆ R of rectangles of total profit at least (1-ε) OPT, where OPT is the profit of an optimum solution, and pack them (either without rotations or with 90o rotations) into the augmented bin [0,1] × [0,1+ε]. This is joint work with Roberto Solis-Oba (Univ. of Western Ontario). Host: Jørgen Bang-Jensen SDU HOME | IMADA HOME | Previous Page Last modified: Tue Sep 11 08:38:17 CEST 2007 Joan Boyar (joan@imada.sdu.dk) |