Coloring and maximum weight independent set of rectangles

Parinya Chalermsook; Bartosz Walczak

doi:10.5555/3458064.3458118

Coloring and maximum weight independent set of rectangles

Parinya Chalermsook^*, Bartosz Walczak

^*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

8 Sitaatiot (Scopus)

Abstrakti

In 1960, Asplund and Grünbaum proved that every intersection graph of axis-parallel rectangles in the plane admits an O(ω²)-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(_log^log_logⁿ_n).

Alkuperäiskieli	Englanti
Otsikko	ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
Toimittajat	Daniel Marx
Kustantaja	ACM
Sivut	860-868
Sivumäärä	9
ISBN (elektroninen)	9781611976465
DOI - pysyväislinkit	https://doi.org/10.5555/3458064.3458118
Tila	Julkaistu - 2021
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	ACM-SIAM Symposium on Discrete Algorithms - Virtual, Online, Alexandria, Yhdysvallat Kesto: 10 tammik. 2021 → 13 tammik. 2021 Konferenssinumero: 32 https://www.siam.org/conferences/cm/conference/soda21

Conference

Conference	ACM-SIAM Symposium on Discrete Algorithms
Lyhennettä	SODA
Maa/Alue	Yhdysvallat
Kaupunki	Alexandria
Ajanjakso	10/01/2021 → 13/01/2021
www-osoite	https://www.siam.org/conferences/cm/conference/soda21

Pääsy asiakirjaan

10.5555/3458064.3458118

https://arxiv.org/abs/2007.07880

OpenUrl-saatavuus

Koko teksti

Muut tiedostot ja linkit

Linkki julkaisuun Scopuksessa

1 Päättynyt
1 Aktiivinen

ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics
Chalermsook, P., Jindal, G., Franck, M., Spoerhase, J., Yingchareonthawornchai, S., Gadekar, A., Orgo, L., Jiamjitrak, W. & Khodamoradi, K.
01/02/2018 → 31/01/2024
Projekti: EU: ERC grants
Kombinatoriikka Graph Pakkaukset ja Online Binary Search Trees.
Chalermsook, P., Uniyal, S., Jiamjitrak, W. & Obscura Acosta, N.
01/09/2017 → 31/08/2020
Projekti: Academy of Finland: Other research funding

Siteeraa tätä

@inproceedings{717ce9ae06ff41f2b00accc03e3d5e58,

title = "Coloring and maximum weight independent set of rectangles",

abstract = "In 1960, Asplund and Gr{\"u}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).",

author = "Parinya Chalermsook and Bartosz Walczak",

note = "| openaire: EC/H2020/759557/EU//ALGOCom ; ACM-SIAM Symposium on Discrete Algorithms, SODA ; Conference date: 10-01-2021 Through 13-01-2021",

year = "2021",

doi = "10.5555/3458064.3458118",

language = "English",

pages = "860--868",

editor = "Daniel Marx",

booktitle = "ACM-SIAM Symposium on Discrete Algorithms, SODA 2021",

publisher = "ACM",

address = "United States",

url = "https://www.siam.org/conferences/cm/conference/soda21",

}

TY - GEN

T1 - Coloring and maximum weight independent set of rectangles

AU - Chalermsook, Parinya

AU - Walczak, Bartosz

N1 - Conference code: 32

PY - 2021

Y1 - 2021

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

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

UR - http://www.scopus.com/inward/record.url?scp=85105252829&partnerID=8YFLogxK

U2 - 10.5555/3458064.3458118

DO - 10.5555/3458064.3458118

M3 - Conference contribution

AN - SCOPUS:85105252829

SP - 860

EP - 868

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

A2 - Marx, Daniel

PB - ACM

T2 - ACM-SIAM Symposium on Discrete Algorithms

Y2 - 10 January 2021 through 13 January 2021

ER -

Coloring and maximum weight independent set of rectangles

Abstrakti

Conference

Pääsy asiakirjaan

OpenUrl-saatavuus

Muut tiedostot ja linkit

Sormenjälki

Projektit

ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics

Kombinatoriikka Graph Pakkaukset ja Online Binary Search Trees.

Siteeraa tätä