Projects per year
Abstract
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).
Original language | English |
---|---|
Title of host publication | ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 |
Editors | Daniel Marx |
Publisher | ACM |
Pages | 860-868 |
Number of pages | 9 |
ISBN (Electronic) | 9781611976465 |
DOIs | |
Publication status | Published - 2021 |
MoE publication type | A4 Conference publication |
Event | ACM-SIAM Symposium on Discrete Algorithms - Virtual, Online, Alexandria, United States Duration: 10 Jan 2021 → 13 Jan 2021 Conference number: 32 https://www.siam.org/conferences/cm/conference/soda21 |
Conference
Conference | ACM-SIAM Symposium on Discrete Algorithms |
---|---|
Abbreviated title | SODA |
Country/Territory | United States |
City | Alexandria |
Period | 10/01/2021 → 13/01/2021 |
Internet address |
Fingerprint
Dive into the research topics of 'Coloring and maximum weight independent set of rectangles'. Together they form a unique fingerprint.Projects
- 2 Finished
-
ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics
Chalermsook, P. (Principal investigator), Jindal, G. (Project Member), Franck, M. (Project Member), Khodamoradi, K. (Project Member), Yingchareonthawornchai, S. (Project Member), Gadekar, A. (Project Member), Orgo, L. (Project Member), Jiamjitrak, W. (Project Member) & Spoerhase, J. (Project Member)
01/02/2018 → 31/01/2024
Project: EU: ERC grants
-
Combinatorics of Graph Packing and Online Binary Search Trees
Chalermsook, P. (Principal investigator), Obscura Acosta, N. (Project Member), Uniyal, S. (Project Member) & Jiamjitrak, W. (Project Member)
01/09/2017 → 31/08/2020
Project: Academy of Finland: Other research funding