Electrical Engineering and Computer Science
menu MENU

Theory Seminar

Coloring and Maximum Weight Independent Set of Rectangles

Parinya ChalermsookAssistant ProfessorAalto University

(Click “Event Website” above to access the zoom link.)

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(log n log log n).


Greg Bodwin


Euiwoong Lee