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: PackungsproblemBin-Packing-ProblemApproximationsalgorithmusZweidimensionales Packungsproblem Free key words: Onlinealgorithmusbin packing problemstrip packing problemapproximation algorithmtwo-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-34702hdl:20.500.11880/26069http://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