Coloring and maximum weight independent set of rectangles

Parinya Chalermsook*, Bartosz Walczak

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

21 Sitaatiot (Scopus)

Abstrakti

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).

AlkuperäiskieliEnglanti
OtsikkoACM-SIAM Symposium on Discrete Algorithms, SODA 2021
ToimittajatDaniel Marx
KustantajaACM
Sivut860-868
Sivumäärä9
ISBN (elektroninen)9781611976465
DOI - pysyväislinkit
TilaJulkaistu - 2021
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaACM-SIAM Symposium on Discrete Algorithms - Virtual, Online, Alexandria, Yhdysvallat
Kesto: 10 tammik. 202113 tammik. 2021
Konferenssinumero: 32
https://www.siam.org/conferences/cm/conference/soda21

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms
LyhennettäSODA
Maa/AlueYhdysvallat
KaupunkiAlexandria
Ajanjakso10/01/202113/01/2021
www-osoite

Sormenjälki

Sukella tutkimusaiheisiin 'Coloring and maximum weight independent set of rectangles'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä