Sprungmarken

Servicenavigation

Fakult? f? Mathematik

Hauptnavigation



Sie sind hier:

Bereichsnavigation



Hauptinhalt

Vorlesung "Approximationsverfahren für diskrete Optimierungsprobleme"

Aktuelles

  • Die Vorlesung beginnt am Donnerstag, 12.10.2017, um 10:15 Uhr (erste Vorlesungswoche).
  • Die Übungen beginnen am Freitag, 20.10.2017 (zweite Vorlesungswoche).

Allgemeine Informationen



Inhalt

Die Veranstaltung "Approximationsverfahren für diskrete Optimierungsprobleme" schließt sich inhaltlich an die Vorlesung "Diskrete Optimierung" an. Gegenstand 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.

In den Übungen soll das erworbene Wissen aus der Vorlesung vertieft werden und anhand von Beispielen angewendet werden.

Skript

Kein Skript vorhanden.

Übungsblätter


Begleitend zur Vorlesung werden wöchentlich Übungsblätter ausgegeben. Diese Übungsblätter werden in moodle veröffentlicht. Hierzu müssen Sie sich bei moodle anmelden. Die Aktivierung der Einschreibemöglichkeit erfolgt im Anschluss an die erste Vorlesung.
Um sich für den Kurs anzumelden, gehen Sie bitte auf den folgenden Link und loggen sich dort unter Ihrem Benutzernamen ein. Danach wählen Sie den Kurs "Approximationsverfahren für diskrete Optimierungsprobleme" aus. Sie werden dann gebeten, einen Einschreibeschlüssel einzugeben. Der Einschreibeschlüssel wird Ihnen in der ersten Vorlesung mitgeteilt.

Studienleistung und Abschlussprüfung

Diese Veranstaltung kann benotet mit einer Abschlussprüfung oder mit einer Studienleistung als unbenotetes Basismodul abgeschlossen werden. Weitere Angaben hierzu werden in der ersten Vorlesung bekannt gegeben und in Moodle bereitgestellt.

Empfohlene Literatur zur Vorlesung

  • G Ausiello, P Crescenzi, G Gambosi, V Kann, A Marchetti-Spaccamela, M Protasi. Complexity and Approximation - Combinatorial Optimization Problems and Their Approximability Properties, Springer, 2003.
  • VV Vazirani. Approximation Algorithms. Springer, 2003.
  • R Wanka. Approximationsalgorithmen - Eine Einführung. Teubner 2006.

Weitere Literaturhinweise werden ggf. in der Vorlesung oder in den Übungen bekannt gegeben.

Links

Lehrstuhl V
Fakultät für Mathematik
TU Dortmund