Two-dimensional packing problems

In both problems, a list of rectangles has to be packed into a designated area such that no two rectangles overlap and all rectangles are packed axis-parallel. For the strip packing problem, the given items have to be packed into a strip of unit width and minimal height, whereas in the two-dimensional bin packing problem a packing has to be found into a minimal number of unit-sized bins.

We investigate approximation algorithms and online algorithms for these problems and consider variants where rotations of the rectangles are forbidden and where rotations by 90 degrees are allowed. In this talk we present selected results from the thesis, namely a 1.9396-approximation algorithm for strip packing and a 2-approximation algorithm for two-dimensional bin packing. Moreover, we outline the main ideas for an improved lower bound of 2.589 on the competitive ratio of online strip packing along with an upper bound of 2.618 for restricted input instances.