Projects per year
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(logloglognn).
|Title of host publication||ACM-SIAM Symposium on Discrete Algorithms, SODA 2021|
|Number of pages||9|
|Publication status||Published - 2021|
|MoE publication type||A4 Article in a conference publication|
|Event||ACM-SIAM Symposium on Discrete Algorithms - Virtual, Online, Alexandria, United States|
Duration: 10 Jan 2021 → 13 Jan 2021
Conference number: 32
|Conference||ACM-SIAM Symposium on Discrete Algorithms|
|Period||10/01/2021 → 13/01/2021|
FingerprintDive into the research topics of 'Coloring and maximum weight independent set of rectangles'. Together they form a unique fingerprint.
01/02/2018 → 31/01/2024
Project: EU: ERC grants
01/09/2017 → 31/08/2020
Project: Academy of Finland: Other research funding