SEMINARIO
| 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 |
|
Resumen 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. --------------------------------------- Important 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 (miguel-f.anjos@polymtl.ca) |
