Groupe d’études et de recherche en analyse des décisions

Matrix relaxations for graph optimization problems

Franz Rendl

Semidefinite programs (SDP) have turned out to be a powerful modeling tool in combinatorial optimization. In this talk, we focus on matrix relaxations of NP-hard graph optimization problems, which lead to SDP and also to other conic programs. While SDP relaxations are usually tractable, the relaxations based on the cone of completely positive matrices are difficult. Relaxations based on this cone often provide exact formulations of the underlying integer problem.

We show some recent developments related to max-k-cut, coloring and some other graph optimization problems.

The resulting SDP are typically of sizes, not accessible by standard algorithmic tools such as interior point methods. We therefore also discuss some very recent algorithmic developments to solve these relaxations and present computational results.

This talk is summarizes work that I have done (jointly with several co-workers) over the past years.