you're reading...

SACT Seminar: Approximation Schemes for Maximum Weight Independent Set of Rectangles

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



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 61 other followers

%d bloggers like this: