Vorlesungsverzeichnis 

Vorlesung im Detail

Approximationsverfahren für diskrete Optimierungsprobleme

Nummer
011404, WS1718
Dozentinnen und Dozenten
Veranstaltungstyp (SWS)
Vorlesung (4+2)
Ort und Zeit
  • M/911 Do 10:00 2h
  • M/911 Fr 12:00 2h
Modul-Zugehörigkeit (ohne Gewähr)
  • DPL:B:-:2
  • DPL:E:-:-
  • MAMA:-:7:MAT-754
  • WIMAMA:-:7:MAT-754
  • TMAMA:-:7:MAT-754
Sprechstunde zur Veranstaltung
Anmeldung?
ohne Angabe
Erforderliche Voraussetzungen
Optimierung (MAT-212), Diskrete Optimierung (MAT-419)
Inhalt
Gegenstand dieser Veranstaltung sind effiziente Verfahren zur Bestimmung von approximativen Lösungen für schwierige diskrete Optimierungsprobleme. Es werden aktuelle Techniken für das Design von Approximationsverfahren anhand klassischer kombinatorischer Optimierungsprobleme behandelt. Ein besonderer Fokus liegt dabei auf der Analyse der vorgestellten Approximationsverfahren hinsichtlich ihrer absoluten bzw. relativen Güte sowie auf der Klassifizierung der betrachteten Optimierungsprobleme bezüglich ihrer Approximierbarkeit. Einen weiteren Schwerpunkt bilden Reduktionstechniken, mit deren Hilfe die Mitgliedschaft bzw. die Nicht-Mitgliedschaft von Optimierungsproblemen in bestimmten Approximationsklassen nachgewiesen werden kann.
Bemerkungen
Link zum Modulhandbuch Mathematik
Empfohlene Literatur
  • G Ausiello, P Crescenzi, G Gambosi, V Kann, A Marchetti-Spaccamela, M Protasi. Complexity and Approximation. Springer, 1999.
  • VV Vazirani. Approximation Algorithms, Springer, 2003.
  • R Wanka. Approximationsalgorithmen - Eine Einführung, Teubner, 2006.

Übung zur Veranstaltung

Nummer der Übung
011405
Übungsgruppen
  • M/911 Fr 14:00 2h

« (zurück) zum Vorlesungsverzeichnis