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;
Leistungskontrolle
Information zur Leistungskontrolle (gültig bis die Lerneinheit neu gelesen wird)
Die Leistungskontrolle wird nur in der Session nach der Lerneinheit angeboten. Die Repetition ist nur nach erneuter Belegung möglich.
Prüfungsmodus
mündlich 30 Minuten
Zusatzinformation zum Prüfungsmodus
70% of the final grade are determined by a 30 minute oral exam with 30 minute preparation time. 30% are determined by the achieved points on specially marked exercise sets throughout the semester.
Diese Angaben können noch zu Semesterbeginn aktualisiert werden; verbindlich sind die Angaben auf dem Prüfungsplan.