Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Approximation Algorithms for Packing Problems
Speaker:Andreas Wiese
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:Joint Lecture Series
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Wednesday, 7 May 2014
Duration:60 Minutes
Building:E1 5
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.

Name(s):Jennifer Müller
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Jennifer Müller, 05/02/2014 10:24 AM
  • Jennifer Müller, 04/04/2014 09:42 AM -- Created document.