DocumentCode :
655207
Title :
Approximation Schemes for Maximum Weight Independent Set of Rectangles
Author :
Adamaszek, Anna ; Wiese, Andreas
Author_Institution :
Max-Planck-Inst. fur Inf., Saarbrücken, Germany
fYear :
2013
fDate :
26-29 Oct. 2013
Firstpage :
400
Lastpage :
409
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 + ε)-approximation algorithm for the MWISR problem with quasipolynomial running time 2poly(log n/ε). In contrast, the best known polynomial time approximation algorithms for the problem achieve superconstant approximation ratios of O(log log n) (unweighted case) and O(log n/log log 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. [4] this allows us to upper bound our approximation ratio by 1 + ε. Our dynamic program is very general and we believe that it will be useful for other settings. In particular, we show that, when parametrized properly, it provides a polynomial time (1 + ε)-approximation for the special case of the MWISR problem when each rectangle is relatively large in at least one dimension. Key to this analysis is a method to tile the plane in order to approximately describe the topology of these rectangles in an optimal solution. This technique might be a useful insight to design better polynomial time approximation algorithms or even a PTAS for the MWISR problem. In particular, note that our results imply that the MWISR problem is not APX-hard, unless NP &#x- 286; DTIME(2polylog (n)).
Keywords :
computational complexity; dynamic programming; graph theory; polynomial approximation; MWISR problem; PTAS; approximation ratio; bounded complexity; geometric dynamic program; maximum weight independent set of rectangles problem; maximum weight subset; n axis-parallel rectangles; pairwise nonoverlapping rectangles; polynomial time approximation algorithms; quasipolynomial running time; superconstant approximation ratios; weighted planar graph separator theorem; Approximation algorithms; Approximation methods; Face; Heuristic algorithms; Partitioning algorithms; Polynomials; Shape;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on
Conference_Location :
Berkeley, CA
ISSN :
0272-5428
Type :
conf
DOI :
10.1109/FOCS.2013.50
Filename :
6686176
Link To Document :
بازگشت