Printable version

Título Matrix relaxations for graph optimization problems
Conferenciante RENDL, Franz (Alpen-Adria Universitaet Klagenfurt, Austria)
[sitio web]  
Fecha jueves, el 15 de septiembre 2011
Hora 15h45
Lugar Salle 5340, Pavillon André-Aisenstadt
Campus de l'Université de Montréal
2920, chemin de la Tour
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.



Ce séminaire vous permettra d’échanger avec le conférencier et les chercheurs présents autour de boissons et de collations. De ce fait, vous devez obligatoirement vous y inscrire. Veuillez prendre note que le nombre de places est limité à 50 participants.

This seminar will give you the opportunity to meet the speaker and all the researchers in attendance while enjoying drinks and snacks. Therefore, you must be registered. The number of participants is limited to 50.

Organizador Miguel F. Anjos (

 Printable version