Title: Closing the gap for pseudo-polynomial strip packing,
Abstract: The set of 2-dimensional packing problems builds an important class of
optimization problems and Strip Packing together with 2-dimensional Bin Packing
and 2-dimensional Knapsack is one of the most famous of these problems. Given a
set of rectangular axis parallel items and a strip with bounded width and
infinite height the objective is to find a packing of the items into the strip
which minimizes the packing height. We speak of pseudo-polynomial Strip Packing
if we consider algorithms with pseudo-polynomial running time with respect to
the width of the strip.
It is known that there is no pseudo-polynomial algorithm for Strip Packing
with a ratio better than $5/4$ unless $\mathrm{P} = \mathrm{NP}$. The best
algorithm so far has a ratio of $(4/3 + \varepsilon)$. In this paper, we close
this gap between inapproximability result and best known algorithm by
presenting an algorithm with approximation ratio $(5/4 + \varepsilon)$ and thus
categorize the problem accurately. The algorithm uses a structural result which
states that each optimal solution can be transformed such that it has one of a
polynomial number of different forms. The strength of this structural result is
that it applies to other problem settings as well for example to Strip Packing
with rotations (90 degrees) and Contiguous Moldable Task Scheduling. This fact
enabled us to present algorithms with approximation ratio $(5/4 + \varepsilon)$
for these problems as well.