252-1426-00L  Approximation Algorithms and Semidefinite Programming

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



Lehrveranstaltungen

NummerTitelUmfangDozierende
252-1426-00 VApproximation Algorithms and Semidefinite Programming3 Std.
Do11:15-12:00HG E 33.3 »
Fr10:15-12:00CAB G 52 »
B. Gärtner, J. Matousek
252-1426-00 UApproximation Algorithms and Semidefinite Programming2 Std.
Di16:15-18:00CAB G 15.2 »
B. Gärtner, J. Matousek
252-1426-00 AApproximation Algorithms and Semidefinite Programming1 Std.B. Gärtner, J. Matousek

Katalogdaten

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;

Leistungskontrolle

Information zur Leistungskontrolle (gültig bis die Lerneinheit neu gelesen wird)
Leistungskontrolle als Semesterkurs
ECTS Kreditpunkte7 KP
PrüfendeB. Gärtner, J. Matousek
FormSessionsprüfung
PrüfungsspracheEnglisch
RepetitionDie Leistungskontrolle wird nur in der Session nach der Lerneinheit angeboten. Die Repetition ist nur nach erneuter Belegung möglich.
Prüfungsmodusmündlich 30 Minuten
Zusatzinformation zum Prüfungsmodus70% 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.

Lernmaterialien

 
HauptlinkThe web page for this lecture, containing all up-to-date course information
Es werden nur die öffentlichen Lernmaterialien aufgeführt.

Gruppen

Keine Informationen zu Gruppen vorhanden.

Einschränkungen

Keine zusätzlichen Belegungseinschränkungen vorhanden.

Angeboten in

StudiengangBereichTyp
Informatik MasterWahlfächer der Vertiefung in Theoretical Computer ScienceWInformation
Mathematik BachelorAuswahl: Mathematische Optimierung, Diskrete Mathematik, InformatikWInformation
Mathematik MasterAuswahl: Mathematische Optimierung, Diskrete Mathematik, InformatikWInformation
Rechnergestützte Wissenschaften BachelorWahlfächerWInformation
Rechnergestützte Wissenschaften MasterWahlfächerWInformation
Zertifikatslehrgang in InformatikFokusfächer und WahlfächerWInformation