Please use this identifier to cite or link to this item: doi:10.22028/D291-26013
Title: Two-dimensional packing problems
Author(s): Harren, Rolf
Language: English
Year of Publication: 2010
SWD key words: Packungsproblem
Bin-Packing-Problem
Approximationsalgorithmus
Zweidimensionales Packungsproblem
Free key words: Onlinealgorithmus
bin packing problem
strip packing problem
approximation algorithm
two-dimensional packing problem
DDC notations: 004 Computer science, internet
Publikation type: Dissertation
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.
Link to this record: urn:nbn:de:bsz:291-scidok-34702
hdl:20.500.11880/26069
http://dx.doi.org/10.22028/D291-26013
Advisor: Weikum, Gerhard
Date of oral examination: 15-Oct-2010
Date of registration: 27-Dec-2010
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
Dissertation_1302_Harr_Rolf_2010.pdf1,57 MBAdobe PDFView/Open


Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.