MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Approximation Algorithms for Packing Problems

Andreas Wiese
Max-Planck-Institut für Informatik - D1
Joint Lecture Series
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI  
Public Audience
English

Date, Time and Location

Wednesday, 7 May 2014
12:15
60 Minutes
E1 5
002
Saarbrücken

Abstract

Packing problems belong to the classical problems in combinatorial optimization.

The most well-known problem of this type is probably the Knapsack problem
in which one seeks to select the most profitable subset of some given items such that
the selected items fit into a knapsack of bounded size. In this talk, I will first present
some recent approximation results on a problem which can be seen as the temporal
extension of Knapsack: each item needs space in the knapsack only during some given
time interval and one has to ensure that at each point in time the items being active
at this time fit into the knapsack. Surprisingly, this problem has connections to a
geometric version of the well-studied Independent Set problem: given a set of
axis-parallel rectangles in the plane, one seeks to find a subset of maximum total
weight such that the selected rectangles are non-overlapping. In the second part
of the talk I will show some new results for this problem whose methods are inspired
by techniques for the above generalization of Knapsack.

Contact

Jennifer Müller
2900
--email hidden
passcode not visible
logged in users only

Jennifer Müller, 05/02/2014 10:24
Jennifer Müller, 04/04/2014 09:42 -- Created document.