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

^*Corresponding author for this work

Jagiellonian University in Kraków

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

11 Citations (Scopus)

Abstract

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

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	https://doi.org/10.5555/3458064.3458118
Publication status	Published - 2021
MoE publication type	A4 Article in a 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	https://www.siam.org/conferences/cm/conference/soda21

Access to Document

10.5555/3458064.3458118

https://arxiv.org/abs/2007.07880

OpenUrl availability

Full text

Cite this

@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

Abstract

Conference

Access to Document

OpenUrl availability

Other files and links

Fingerprint

ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics

Combinatorics of Graph Packing and Online Binary Search Trees

Cite this

Coloring and maximum weight independent set of rectangles

Abstract

Conference

Access to Document

OpenUrl availability

Other files and links

Fingerprint

Projects

ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics

Combinatorics of Graph Packing and Online Binary Search Trees

Cite this