Vorlesung im Detail
Approximationsverfahren für diskrete Optimierungsprobleme
Nummer011404, WS1718Dozentinnen und DozentenVeranstaltungstyp (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 VeranstaltungAnmeldung?ohne AngabeErforderliche VoraussetzungenOptimierung (MAT-212), Diskrete Optimierung (MAT-419)InhaltGegenstand 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. BemerkungenLink zum Modulhandbuch MathematikEmpfohlene 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 Übung011405Übungsgruppen « (zurück) zum Vorlesungsverzeichnis