How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking
How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking
复制标题
如何驯服矩形：通过收缩解决矩形的独立集和着色问题
DOI：
10.4230/lipics.approx-random.2015.43
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Andreas Wiese
中科院分区：
文献类型：
--
作者：
Anna Adamaszek;Parinya Chalermsook;Andreas Wiese
在最大权独立矩形集（MWISR）问题中，我们给出了一个平面上的加权轴平行矩形集。我们的目标是计算成对不重叠矩形的最大权重子集。由于它的各种应用，以及连接到计算机科学中的许多其他问题，MWISR已经收到了大量的关注，从计算几何和近似算法社区。然而，尽管被广泛研究，MWISR在多项式时间近似算法方面仍然没有得到很好的理解，因为在上限和下限之间存在很大的差距，即，O（log n\ loglog n）vs. NP-硬度。另一个重要的，不太容易理解的问题是，是否可以用至多O（omega（R））种颜色对矩形进行着色，其中omega（R）是一组输入矩形R的相交图中的最大团的大小。阿斯普朗德和格伦鲍姆在大约50年前得到了O（omega（R）^2）的上界，并且这个结果一直是渐近最好的。这个问题与MWISR的规范LP的完整性间隙密切相关。
在本文中，我们解决了上述三个开放的问题，在一个放松的模型中，我们被允许缩小矩形一点点（重新缩放它们的因子为1-delta，对于任意小的常数delta > 0。也就是说，在这个模型中，我们显示（i）一个PTAS的MWISR和（ii）一个着色与O（ω（R））的颜色，这意味着一个恒定的上界的完整性间隙的典型LP。
对于MWISR的某些应用，缩小矩形的可能性具有自然的、动机良好的意义。我们的研究结果可以被看作是一个证据，收缩模型是一个有前途的方法来放松几何问题的目的，更好的算法结果。
In the Maximum Weight Independent Set of Rectangles (MWISR) problem, we are given a collection of weighted axis-parallel rectangles in the plane. Our goal is to compute a maximum weight subset of pairwise non-overlapping rectangles. Due to its various applications, as well as connections to many other problems in computer science, MWISR has received a lot of attention from the computational geometry and the approximation algorithms community. However, despite being extensively studied, MWISR remains not very well understood in terms of polynomial time approximation algorithms, as there is a large gap between the upper and lower bounds, i.e., O(log n\ loglog n) v.s. NP-hardness. Another important, poorly understood question is whether one can color rectangles with at most O(omega(R)) colors where omega(R) is the size of a maximum clique in the intersection graph of a set of input rectangles R. Asplund and Grunbaum obtained an upper bound of O(omega(R)^2) about 50 years ago, and the result has remained asymptotically best. This question is strongly related to the integrality gap of the canonical LP for MWISR.
In this paper, we settle above three open problems in a relaxed model where we are allowed to shrink the rectangles by a tiny bit (rescaling them by a factor of 1-delta for an arbitrarily small constant delta > 0. Namely, in this model, we show (i) a PTAS for MWISR and (ii) a coloring with O(omega(R)) colors which implies a constant upper bound on the integrality gap of the canonical LP.
For some applications of MWISR the possibility to shrink the rectangles has a natural, well-motivated meaning. Our results can be seen as an evidence that the shrinking model is a promising way to relax a geometric problem for the purpose of better algorithmic results.