# Coloring and Maximum Weight Independent Set of Rectangles

arXiv: https://arxiv.org/abs/2007.07880 · HTML: https://mlsanity.com/paper/2007.07880/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jul 2020.

## Built on by (most cited first, 1 of 1)

- [Approximation Algorithms for ROUND-UFP and ROUND-SAP](https://mlsanity.com/paper/2202.03492/) (2022)

## Abstract (arXiv)

In 1960, Asplund and Gr"unbaum 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(loglog n)-approximation algorithm for the maximum weight independent set problem in axis-parallel rectangles, which improves on the previous approximation ratio of O(fraclog nloglog n).