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 article in proceedingsScientificpeer-review

23 Citations (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
PublisherACM
Pages860-868
Number of pages9
ISBN (Electronic)9781611976465
DOIs
Publication statusPublished - 2021
MoE publication typeA4 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
Country/TerritoryUnited 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.
  • ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics

    Chalermsook, P. (Principal investigator), Jindal, G. (Project Member), Franck, M. (Project Member), Khodamoradi, K. (Project Member), Yingchareonthawornchai, S. (Project Member), Gadekar, A. (Project Member), Orgo, L. (Project Member), Jiamjitrak, W. (Project Member) & Spoerhase, J. (Project Member)

    01/02/201831/01/2024

    Project: EU: ERC grants

  • Combinatorics of Graph Packing and Online Binary Search Trees

    Chalermsook, P. (Principal investigator), Obscura Acosta, N. (Project Member), Uniyal, S. (Project Member) & Jiamjitrak, W. (Project Member)

    01/09/201731/08/2020

    Project: Academy of Finland: Other research funding

Cite this