Improved approximation for two dimensional Strip Packing with polynomial bounded width

We study the well-known two-dimensional Strip Packing problem. Given a set of rectangular axis-parallel items and a strip of width W with infinite height, the objective is to find a packing of all items into the strip, which minimizes the packing height. Lately, it has been shown that the lower bound of 3/2 of the absolute approximation ratio can be beaten when we allow a pseudo-polynomial running-time of type ( n W ) f ( 1 / ε ). If W is polynomially bounded by the number of items, this is a polynomial running-time. The currently best pseudo-polynomial approximation algorithm by Nadiradze and Wiese achieves an approximation ratio of 1. 4 + ε. We present a pseudo-polynomial algorithm with improved approximation ratio 4 / 3 + ε. Furthermore, the presented algorithm has a significantly smaller running-time as the 1. 4 + ε approximation algorithm.

Authors

• Klaus Jansen
• Malin Rau

Keywords

• Strip Packing
• Pseudo polynomial
• Structural Lemma
• Approximation Algorithm