Coloring and maximum weight independent set of rectangles

Parinya Chalermsook*, Bartosz Walczak

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

1 Citation (Scopus)

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 languageEnglish
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2021
EditorsDaniel Marx
PublisherAssociation for Computing Machinery (ACM)
Pages860-868
Number of pages9
ISBN (Electronic)9781611976465
DOIs
Publication statusPublished - 2021
MoE publication typeA4 Article in a conference publication
EventACM-SIAM Symposium on Discrete Algorithms - Virtual, Online, Alexandria, United States
Duration: 10 Jan 202113 Jan 2021
Conference number: 32
https://www.siam.org/conferences/cm/conference/soda21

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSODA
CountryUnited States
CityAlexandria
Period10/01/202113/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.

Cite this