Coloring and maximum weight independent set of rectangles
No Thumbnail Available
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
Other link related to publication (opens in new window)
Authors
Date
2021
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
9
Series
ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pp. 860-868
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).Description
| openaire: EC/H2020/759557/EU//ALGOCom
Keywords
Other note
Citation
Chalermsook, P & Walczak, B 2021, Coloring and maximum weight independent set of rectangles . in D Marx (ed.), ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 . ACM, pp. 860-868, ACM-SIAM Symposium on Discrete Algorithms, Alexandria, Virginia, United States, 10/01/2021 . https://doi.org/10.5555/3458064.3458118