Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems

We consider the two-dimensional bin packing and strip packing problem, where a list of rectangles has to be packed into a minimal number of rectangular bins or a strip of minimal height, respectively. All packings have to be non-overlapping and orthogonal, i.e., axis-parallel. Our algorithm for strip packing has an absolute approximation ratio of $1.9396$ and is the first algorithm to break the approximation ratio of 2 which was established more than a decade ago. Moreover, we present an algorithm for two-dimensional bin packing with an absolute worst-case ratio of 2, which is optimal provided $\mathcal{P} \not= \mathcal{NP}$