Maximum independent set of rectangles

Maximum independent set of rectangles
复制标题

最大独立矩形集

DOI：
10.1137/1.9781611973068.97
复制
发表时间：
2009
期刊：
SIAM J. Comput.
影响因子：
--
通讯作者：
Julia Chuzhoy
Julia Chuzhoy
中科院分区：
--
文献类型：
--
作者：
Parinya Chalermsook;Julia Chuzhoy

文献摘要

被引文献

相似文献

我们研究了最大独立矩形集（MISR）问题：给定一个n轴平行矩形的集合R，找出不相交矩形的最大基数子集。MISR是经典的最大独立集问题的一种特殊情况，其中输入被限制为轴平行矩形的相交图。由于它的许多应用，从地图标注到数据挖掘，MISR受到了各种研究团体的极大关注。由于该问题是NP-难的，主要的焦点一直是近似算法的设计。几组研究独立建议O（log n）-近似算法MISR，这仍然是目前已知的最好的近似因子的问题。本文的主要结果是一个O（log log n）-近似算法MISR。我们的算法结合了现有的方法来解决特殊情况下的问题，其中输入的矩形集被限制为包含特定的交叉类型，与新的见解，在平面上相交的矩形集的组合结构。 我们还考虑了MISR的推广到更高的维度，其中矩形由d维超矩形取代。我们对MISR的结果意味着这个问题的O（（log n）d−2 log log n）-近似算法，改进了以前已知的最好的O（（log n）d−1）-近似。
We study the Maximum Independent Set of Rectangles (MISR) problem: given a collection R of n axis-parallel rectangles, find a maximum-cardinality subset of disjoint rectangles. MISR is a special case of the classical Maximum Independent Set problem, where the input is restricted to intersection graphs of axis-parallel rectangles. Due to its many applications, ranging from map labeling to data mining, MISR has received a significant amount of attention from various research communities. Since the problem is NP-hard, the main focus has been on the design of approximation algorithms. Several groups of researches have independently suggested O(log n)-approximation algorithms for MISR, and this remained the best currently known approximation factor for the problem. The main result of our paper is an O(log log n)-approximation algorithm for MISR. Our algorithm combines existing approaches for solving special cases of the problem, in which the input set of rectangles is restricted to containing specific intersection types, with new insights into the combinatorial structure of sets of intersecting rectangles in the plane. We also consider a generalization of MISR to higher dimensions, where rectangles are replaced by d-dimensional hyper-rectangles. Our results for MISR imply an O((log n)d−2 log log n)-approximation algorithm for this problem, improving upon the best previously known O((log n)d−1)-approximation.