Coloring and Maximum Weight Independent Set of Rectangles

Speaker: Bartosz Walczak (Jagiellonian University)

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 n/ log log n). Joint work with Parinya Chalermsook.

Date and time: 11/03/2021 at 14:30 (Paris time)

Link to the talk: