Coloring and Maximum Weight Independent Set of Rectangles
Coloring and Maximum Weight Independent Set of Rectangles
复制标题
独立矩形组的着色和最大重量
DOI：
10.1137/1.9781611976465.54
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Bartosz Walczak
中科院分区：
文献类型：
--
作者：
Parinya Chalermsook;Bartosz Walczak
1960年，Asplund和Grunbaum证明了平面上平行轴矩形的交图都有$O（\omega ^2）$-染色，其中$\omega$是团的最大尺寸。我们提出了第一个渐进的改进，在这个六十岁的界限，证明了每个这样的图是O（\omega\log\omega）$-着色，并提出了一个多项式时间算法，找到这样的着色。这一改进导致了一个多项式时间的$O（\log\log n）$-近似算法的最大重量独立集问题的轴平行矩形，提高了以前的近似比$O（\frac{\log n}{\log\log n}）$。
In 1960, Asplund and Grunbaum proved that every intersection graph of axis-parallel rectangles in the plane admits an $O(\omega^2)$-coloring, where $\omega$ is the maximum size of a clique. We present the first asymptotic improvement over this six-decade-old bound, proving that every such graph is $O(\omega\log\omega)$-colorable and presenting a polynomial-time algorithm that finds such a coloring. This improvement leads to a polynomial-time $O(\log\log n)$-approximation algorithm for the maximum weight independent set problem in axis-parallel rectangles, which improves on the previous approximation ratio of $O(\frac{\log n}{\log\log n})$.