论文标题
着色和最大重量独立的矩形集
Coloring and Maximum Weight Independent Set of Rectangles
论文作者
论文摘要
1960年，Asplund和Grünbaum证明了飞机中轴平行矩形的每个相交图都承认$ O（ω^2）$ - 着色，其中$ω$是一个集团的最大尺寸。我们介绍了对这个六十年历史的结合的第一个渐近改进，证明了每个图形都是$ O（ω\logΩ）$ - 可着色，并呈现一种多项式时算法，可以找到这种着色。此改进会导致多项式时间$ O（\ log \ log n）$ - 在轴平行矩形中最大重量独立设置问题的近似算法，该矩形的最大重量独立集问题，该算法的上一个近似值（\ frac {\ frac {\ log n} {\ log log \ log \ n}）的上一个近似值提高了。
In 1960, Asplund and Grünbaum proved that every intersection graph of axis-parallel rectangles in the plane admits an $O(ω^2)$-coloring, where $ω$ 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(ω\logω)$-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})$.
