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

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.

This is joint work with Anna Adamaszek

### Like this:

Like Loading...

*Related*

## Discussion

## No comments yet.