Treffer: Approximation Algorithms for Geometric Packing Problems ; Approximative Algorithmen für geometrische Packungsprobleme

In this thesis we present approximation algorithms for two-dimensional, geometric packing problems. We have given a set of rectangles that have to be placed in one or several predetermined target regions. Such packing problems can be found in several branches of industry, for example when placing logic elements on a chip, or when cutting stock. We consider three problems in detail. First, the so-called two-dimensional strip packing problem consists of a set of rectangles and a strip of width 1 and infinite height. The objective is to find an axis-parallel and non-overlapping arrangement of the rectangles in this strip in order to minimize the total packing height. Furthermore, it is not allowed to rotate the rectangles. For any eps>0, we present an approximation algorithm with an absolute approximation ratio of 5/3+\eps for this problem. The second problem that we study is the two-dimensional bin packing problem. For this problem a set of rectangles is given as input again. The objective is to find an axis-parallel and non-overlapping packing of all rectangles into the minimum number of unit-sized squares, which are also called bins. We consider two versions of this problem. In the first version, we are allowed to rotate the rectangles by 90°, i.e. to exchange the widths and the heights of the rectangles. In the second version it is not allowed to rotate the rectangles at all. For both versions, our result is an approximation algorithm with an asymptotic approximation ratio of 3/2+eps for an arbitrary value eps>0. For the third problem, we have given a set of rectangles of heights 1 and arbitrary widths and a strip of a given integral height and infinite width. The objective is to find an axis-parallel and non-overlapping packing of the rectangles into the strip so that the maximum packing width is minimized. In this setting, it is not allowed to rotate the rectangles. This problem is also known as scheduling problem, with machines representing the strip and jobs representing the rectangles. The definition ...