Title: Approximation Schemes for Maximum Weight Independent Set of Rectangles
Abstract:
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.
Joint work with Anna Adamaszek