Two-dimensional packing problems

Abstract

In this thesis we consider the two-dimensional bin packing problem and the strip packing problem, which are popular geometric generalizations of the classical bin packing problem. 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 particular, we present two approximation algorithms for strip packing with approximation ratios 1.9396 and arbitrarily close to 5/3,respectively. These results are the first improvements upon the approximation ratio of 2 that was established 16 years ago. Moreover, we show 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. For two-dimensional bin packing we derive best-possible approximation algorithms for the variants with and without rotations.

In dieser Arbeit befassen wir uns mit dem zweidimensionalen Bin Packing Problem und dem Strip Packing Problem. Beide Probleme sind geometrische Verallgemeinerungen des klassischen Bin Packings. Bei beiden Problemen soll eine gegebene Liste an Rechtecken so in einen vorgegebenen Bereich gepackt werden, dass die Rechtecke sich nicht überlappen und alle Rechtecke achsenparallel gepackt sind. Beim Strip Packing soll die Packungshöhe einer Packung der Rechtecke in einen Streifen (Strip) der Breite 1 minimiert werden. Dahingegen erfolgt die Packung beim Bin Packing in eine minimale Anzahl an Quadraten (Bins) der Gröà e 1. Wir untersuchen Approximationsalgorithmen und Onlinealgorithmen für diese Probleme und unterscheiden die Varianten, in denen die Rechtecke nicht rotiert werden dürfen und in denen eine Rotation um 90 Grad erlaubt ist. Für das Strip Packing Problem zeigen wir Approximationsalgorithmen mit Güten 1, 9396 und beliebig nah an 5/3. Dies sind die ersten Verbesserungen der Approximationsgüte von 2 die vor 16 Jahren gezeigt wurde. Des Weiteren zeigen wir eine verbesserte untere Schranke von 2, 589 für das online Strip Packing Problem und geben einen Onlinealgorithmus mit Güte 2, 618 für eingeschränkte Instanzen an. Für das Bin Packing Problem präsentieren wir bestmögliche Algorithmen für die Varianten mit und ohne Rotation.