252-1426-00L  Approximation Algorithms and Semidefinite Programming

SemesterFrühjahrssemester 2012
DozierendeB. Gärtner, J. Matousek
Periodizitätjährlich wiederkehrende Veranstaltung
LehrspracheEnglisch


KurzbeschreibungOver 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.
LernzielStudents 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.
InhaltThe 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
SkriptThe lecture will follow (parts of) the book "Approximation Algorithms and Semidefinite Programming" by the lecturers (see literature).
LiteraturBernd 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 / BesonderesBasic knowledge in linear algebra and analysis; the ability to fill in routine details in proofs;