Two-dimensional packing problems [Elektronische Ressource] / Rolf Harren

Der Universität Des Saarlandes, © Rolf Harren, Der Naturwissenschaftlich-Technischen Fakultäten

Sujets

• Informatik

Informations

• Publié par: universitat_des_saarlandes
• Publié le: 01 janvier 2010
• Nombre de lectures: 12
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

T W O - D I M E N S I O N A L
PA C K I N G P R O B L E M S
rolf harren
Dissertation
zur Erlangung des Grades des Doktors der Naturwissenschaften
der Naturwissenschaftlich-Technischen Fakultäten
der Universität des Saarlandes
Saarbrücken, Juli 2010tag des kolloquiums
15. Oktober 2010
dekan der fakultät 6
Prof. Dr. Holger Hermanns
mitglieder des prüfungsausschusses
Prof. Dr. Gerhard Weikum (Vorsitzender)
PD Dr. Rob van Stee
Prof. Dr. Kurt Mehlhorn
Prof. Dr. Klaus Jansen
Dr. Eric Berberich
ort
Saarbrücken
Rolf Harren: Two-dimensional packing problems, Dissertation, Juli 2010Für AnnalenaA B S T R A C T
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 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 ro-
tations by 90 degrees are allowed. In particular, we present two approximation algo-
rithms 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
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.
Z U S A M M E N FA S S U N G
In dieser Arbeit befassen wir uns mit dem zweidimensionalen Bin Packing Problem
und dem Strip Packing Problem. Beide Probleme sind geometrische Verallgemeine-
rungen des klassischen Bin Packings.
Bei beiden Problemen soll eine gegebene Liste an Rechtecken so in einen vorge-
gebenen Bereich gepackt werden, dass die Rechtecke sich nicht überlappen und alle
Rechtecke achsenparallel gepackt sind. Beim Strip Packing soll die Packungshöhe ei-
ner Packung der Rechtecke in einen Streifen (Strip) der Breite 1 minimiert werden.
Dahingegen erfolgt die Packung beim Bin Packing in eine minimale Anzahl an Qua-
draten (Bins) der Größe 1.
Wir untersuchen Approximationsalgorithmen und Onlinealgorithmen für diese Pro-
bleme und unterscheiden die Varianten, in denen die Rechtecke nicht rotiert werden
dürfen und in denen eine Rotation um90 Grad erlaubt ist. Für das Strip Packing Pro-
blem zeigen wir Appr 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äsentie-
ren wir bestmögliche Algorithmen für die Varianten mit und ohne Rotation.
vP U B L I C AT I O N S
The results presented in this thesis have previously appeared or been submitted as
parts of the following publications:
• R. Harren and R. van Stee. Absolute approximation ratios for packing rectangles
into bins. Journal of Scheduling, 2009, doi:10.1007/s10951-009-0110-3
(A preliminary version was published in SWAT 2008)
• R. Harren and R. van Stee. Improved absolute approximation ratios for two-
dimensional packing problems. In APPROX: Proc. 12th Workshop on Approxima-
tion Algorithms for Combinatorial Optimization Problems, pages 177–189, 2009
• R. Harren, K. Jansen, L. Prädel and R. van Stee. A (5/3+#)-approximation for
strip packing. submitted
The results on online strip packing are based on a joint work with Walter Kern. The
publication of these results is in preparation.
viiA C K N O W L E D G M E N T S
I would like to thank Xin Han for initially introducing me to the topic of multi-
dimensional packing problems during a research stay at Kyoto University. I am thank-
ful to Kazuo Iwama for his hospitality during this research stay and to Ingo Wegener
for his help and encouragement.
Benjamin Doerr was the one to draw my attention to the Max-Planck-Institut für
Informatik. I am thankful to him for that and for the continued mentorship during
my time here. I was very lucky to be part of the MPI, benefitting from the excellent
working conditions and facilities. My thanks go to Kurt Mehlhorn for offering me this
great opportunity. The people in the working group made my stay here pleasant and
enjoyable, especially my room mates Edda Happ and Stefan Kratsch.
The best experiences during my research arouse from collaborations with others.
Therefore, I am grateful to my coauthors Florian Diedrich, Klaus Jansen, Walter Kern,
Lars Prädel, Ralf Thöle, Henning Thomas, and Rob van Stee.
It is probably something of a rarity to be able to pinpoint a personal research break-
through to a specific event. I am very thankful to the anonymous questioner in the
discussion after a presentation at ETH Zürich. One particular question opened my
eyes towards the applicability of the developed methods on a different problem. I
thank Reto Spöhel for his invitation to ETH Zürich and the fruitful discussions.
Special thanks go to my advisor Rob van Stee whose thoughtful comments helped
to improve the presentation of this dissertation.
I am deeply grateful to the support of my family, who never complained seeing
me rarely throughout the last years. Hopefully I will be able to give back at least a
fraction of the unconditional support that I received.
Finally, my biggest thank goes to my wife, Annalena. Your love is of utmost impor-
tance to me. Together with you I am cheerfully looking forward to the next chapters
in our lives.
Rolf Harren
ix