Projects per year
Abstract
In 1960, Asplund and Grünbaum proved that every intersection graph of axisparallel 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 sixdecadeold bound, proving that every such graph is O(ω log ω)colorable and presenting a polynomialtime algorithm that finds such a coloring. This improvement leads to a polynomialtime O(log log n)approximation algorithm for the maximum weight independent set problem in axisparallel rectangles, which improves on the previous approximation ratio of O(_{log}^{log}_{log}^{n}_{n}).
Original language  English 

Title of host publication  ACMSIAM Symposium on Discrete Algorithms, SODA 2021 
Editors  Daniel Marx 
Publisher  Association for Computing Machinery (ACM) 
Pages  860868 
Number of pages  9 
ISBN (Electronic)  9781611976465 
DOIs  
Publication status  Published  2021 
MoE publication type  A4 Article in a conference publication 
Event  ACMSIAM 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  ACMSIAM Symposium on Discrete Algorithms 

Abbreviated title  SODA 
Country  United States 
City  Alexandria 
Period  10/01/2021 → 13/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., Spoerhase, J., Orgo, L. & Yingchareonthawornchai, S.
01/02/2018 → 31/01/2024
Project: EU: ERC grants

Combinatorics of Graph Packing and Online Binary Search Trees
Chalermsook, P., Obscura Acosta, N., Uniyal, S. & Jiamjitrak, W.
01/09/2017 → 31/08/2020
Project: Academy of Finland: Other research funding