TY  - THES
T1  - Two-dimensional packing problems
A1  - Harren,Rolf
Y1  - 2010/12/27
N2  - 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.
KW  - Packungsproblem
KW  - Bin-Packing-Problem
KW  - Approximationsalgorithmus
KW  - Zweidimensionales Packungsproblem
CY  - Saarbrücken
PB  - Universitäts- und Landesbibliothek
AD  - Postfach 151141, 66041 Saarbrücken
UR  - http://scidok.sulb.uni-saarland.de/volltexte/2010/3470
ER  -