Coloring and Maximum Weight Independent Set of Rectangles

DOI10.5555/3458064.3458118MaRDI QIDQ6147304zbMATH OpenOpenAlexFDO

Authors Parinya Chalermsook, Bartosz Walczak

Publication date 15 January 2024

Full work available at URL https://arxiv.org/abs/2007.07880

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: In 1960, Asplund and Gr"unbaum proved that every intersection graph of axis-parallel rectangles in the plane admits an $O(omeg{a}^2)$-coloring, where $omega$ 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(omegalogomega)$-colorable and presenting a polynomial-time algorithm that finds such a coloring. This improvement leads to a polynomial-time $O(loglogn)$-approximation algorithm for the maximum weight independent set problem in axis-parallel rectangles, which improves on the previous approximation ratio of $O(fraclognloglogn)$.

Cited in

(18)

• Geometric stabbing via threshold rounding and factor revealing LPs
• Disjointness graphs of short polygonal chains
• Treewidth versus clique number. II: Tree-independence number
• Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
• Independent set in \(k\)-claw-free graphs: conditional \(\chi \)-boundedness and the power of LP/SDP relaxations
• Stabbing boxes with finitely many axis-parallel lines and flats
• Reuniting -boundedness with polynomial -boundedness
• Approximation of MWIS on geometric intersection graphs
• The -binding function of d-directional segment graphs
• Approximating the maximum independent set of convex polygons with a bounded number of directions
• Graphs of bounded chordality
• Approximation algorithms for round-UFP and round-SAP
• Semi-algebraic and semi-linear Ramsey numbers (extended abstract)
• Recognizing integrality of weighted rectangles partitions
• Polynomial Gyárfás-Sumner conjecture for graphs of bounded boxicity
• Parameterized approximation for maximum weight independent set of rectangles and segments
• Fully dynamic maximum independent sets of disks in polylogarithmic update time
• An improved guillotine cut for squares

This page was built for publication: Coloring and Maximum Weight Independent Set of Rectangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6147304)