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