DATE: Tuesday January 21st, 11am ROOM: IDSIA meeting room, Galleria 1, Manno SPEAKER: Lars Pradel, University of Kiel TITLE: Approximation Algorithms for Geometric Packing Problems ABSTRACT: We present approximation algorithms for two-dimensional, geometric packing problems. For these problems a set of rectangles is given and we are looking for an axis-parallel, non-rotated and non-overlapping packing of these rectangles into 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 geometric knapsack problem with area maximization, which consists of a set of rectangles and a unit-sized square. The objective is to find a subset of the rectangles with a maximum total area that can be packed into the square. We present a polynomial time approximation scheme for this problem. The second problem that we study is the two-dimensional strip packing problem. This problem consists of a set of rectangles and a strip of width $1$ and infinite height. The objective is to find an arrangement of all rectangles in this strip in order to minimize the total packing height. For any $\varepsilon>0$, we present an approximation algorithm with an absolute approximation ratio of $5/3+\varepsilon$ for this problem. For the third problem a set of rectangles is given as input again. The objective of the two-dimensional bin packing problem is to find a packing of all rectangles into the minimum number of unit-sized squares, which are also called bins. Our results are an approximation algorithm with an absolute approximation ratio of $2$ and an algorithm with asymptotic approximation ratio of $3/2+\varepsilon$ for an arbitrary value $\varepsilon>0$.