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:Independent set of convex polygons: from n^eps to 1+eps via shrinking
Speaker:Andreas Wiese
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 28 April 2016
Duration:20 Minutes
Building:E1 4
In the Independent Set of Convex Polygons problem we are given a set of weighted convex polygons in the plane and we want to compute a maximum weight subset of non-overlapping polygons. This is a very natural and well-studied problem with applications in many different areas. Unfortunately, there is a very large gap between the known upper and lower bounds for this problem. The best polynomial time algorithm we know has an approximation ratio of n^epsilon and the best known lower bound shows only strong NP-hardness.

In this paper we close this gap completely, assuming that we are allowed to shrink the polygons a little bit, by a factor 1-delta for an arbitrarily small constant delta>0, while the compared optimal solution cannot do this (resource augmentation). In this setting, we improve the approximation ratio from n^epsilon to 1+epsilon which matches the above lower bound that still holds if we can shrink the polygons.

Name(s):Andreas Wiese
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Andreas Wiese, 04/21/2016 03:58 PM
Last modified:
Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Andreas Wiese, 04/21/2016 03:58 PM -- Created document.