Over the last fifteen years, semidefinite programming has become an important tool for approximate solutions of hard combinatorial problems. In this lecture, we introduce the foundations of semidefinite programming, we present some of its applications in (but not only in) approximation algorithms, and we show how semidefinite programs can efficiently be solved.
Lernziel
Students should understand that semidefinite programs form a well-understood class of optimization problems that can (approximately) be solved in polynomial time and yet are powerful enough to yield good approximate solutions for hard combinatorial problems.
Inhalt
The Goemans-Williamson MAXCUT algorithm. semidefinite programming, The Lovasz theta function, cone programming and duality, algorithms for semidefinite programming, advanced applications of semidefinite programming in approximation algorithms
Skript
The lecture will follow (parts of) the book "Approximation Algorithms and Semidefinite Programming" by the lecturers (see literature).
Literatur
Bernd Gärtner and Jiri Matousek: Approximation Algorithms and Semidefinite Programming, Springer, 2012
David P. Williamson and David B. Shmoys: The Design of Approximation Algorithms, Cambridge University Press, 2011
Voraussetzungen / Besonderes
Basic knowledge in linear algebra and analysis; the ability to fill in routine details in proofs;