Time: 1:00pm Tuesday 22 October
Location: SIT 459
Speaker: Andreas Wiese, Max Planck Institute for Informatics
Title: Approximation Schemes for Maximum Weight Independent Set of Rectangles
In the Maximum Weight Independent Set of Rectangles (MWISR) problem
we are given a set of n axis-parallel rectangles in the 2D-plane,
and the goal is to select a maximum weight subset of pairwise non-overlapping
rectangles. Due to many applications, e.g. in data mining, map labeling
and admission control, the problem has received a lot of attention
by various research communities. We present the first (1+eps)-approximation
algorithm for the MWISR problem with quasi-polynomial running time
2^poly(log n/eps). In contrast, the best known polynomial time
approximation algorithms for the problem achieve superconstant approximation
ratios of O(loglog n) (unweighted case) and O(log n/loglog n) (weighted case).
Key to our results is a new geometric dynamic program which recursively
subdivides the plane into polygons of bounded complexity. We provide
the technical tools that are needed to analyze its performance. In particular, we present a
method of partitioning the plane into small and simple areas such that the rectangles of an optimal
solution are intersected in a very controlled manner. Together with a novel application
of the weighted planar graph separator theorem due to Arora et al.
this allows us to upper bound our approximation ratio by 1+eps.
This is joint work with Anna Adamaszek