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 (nW)(f(1/epsilon)). 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 + epsilon. We present a pseudo-polynomial algorithm with improved approximation ratio 4/3 + epsilon. Furthermore, the presented algorithm has a significantly smaller running-time as the 1.4 + epsilon approximation algorithm. (C) 2019 Elsevier B.V. All rights reserved.