Sprungmarken

Servicenavigation

TU Dortmund

Hauptnavigation


Bereichsnavigation

Nebeninhalt

Studierendenportal

Empfohlene Literatur


Vorlesung

Approximationsverfahren für diskrete Optimierungsprobleme

Nummer
011404, WS1718
Dozentinnen und Dozenten
Veranstaltungstyp
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 – Mathematik, Diplom (auslaufend)
DPL:E:-:- – Mathematik, Promotionsstudiengang
MAMA:-:7:MAT-754
WIMAMA:-:7:MAT-754
TMAMA:-:7:MAT-754
Beginn der Veranstaltung
12.10.2017
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.

Übungen

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