Optimization and Systems Theory Minicourse
Wednesday, June 2, 1999, 15.15-17.00, Room 3733, Lindstedtsv. 25
Thursday, June 3, 13.15-15.00, Room 3733, Lindstedtsv. 25
Friday, June 4, 9.15-11.00, Room 3733, Lindstedtsv. 25

Claude Lemaréchal
Grenoble, France

Lagrangian duality and SDP relaxation in combinatorial optimization

The aim of the tutorial is to overview the SDP relaxation technique for some combinatorial problems, and to embed it in a more general framework: Lagrangian duality. We will start from two well-known instances: the max-cut and max-stable problems. We will show how their SDP relaxations can be recovered as Lagrangian (bi-)duals. This allows us to generalize the approach to large classes of combinatorial problems. We construct tight SDP relaxations of them, which for which we compare with the classical - or linear - Lagrangian relaxation.
Calendar of seminars
Last update: June 2, 1999 by Anders Forsgren, anders.forsgren@math.kth.se.