2016/10/14 by Jansen, Klaus, Rau, Malin
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1610.04430
We study the well-known two-dimensional strip packing problem. Given is a set of rectangular axis-parallel items and a strip of width W with infinite height. The objective is to find a packing of these 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. We present a pseudo-polynomial algorithm with approximation ratio 4/3 +ε and running time (n W)^1/ε^O(21/ε).