Improved approximation for two dimensional strip packing with polynomial bounded width

Abstract

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 $(nW{)}^{f(1/\epsilon )}$. 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+\epsilon$ and running time $(nW{)}^{1/{\epsilon }^{\mathcal{O}(2^{1/\epsilon })}}$.

Research was supported in part by German Research Foundation (DFG) project JA 612 /14-2

References in corpus (1)

• Hardness of approximation for strip packing

Cited by in corpus (1)

• Hardness of approximation for strip packing