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  ACM 
Pages  860868 
Number of pages  9 
ISBN (Electronic)  9781611976465 
DOIs  
Publication status  Published  2021 
MoE publication type  A4 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/Territory  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.Projects
 2 Finished

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/2018 → 31/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/2017 → 31/08/2020
Project: Academy of Finland: Other research funding