Fwd: Postdoc Position at IDSIA
by Announcements of talks＠IDSIA
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$.
11 years, 1 month
- 1
- 0
- ← Newer
- 1
- Older →