Approximationsalgorithmen

Steckbrief

Eckdaten

Studiengang:
Master Betriebswirtschaftslehre
Fachsemester:
4
Veranstaltungstyp:
Vorlesung
Sprache:
Deutsch/Englisch
Turnus:
Unregelmäßig
Zeitplan:
Ganzes Semester
Semesterwochen- stunden:
6.0
Credits:
5.0
Anwesendheits- pflicht:
Nein

Dozent

  • Univ.-Prof. Dr.rer.nat. Marco Lübbecke

Die folgenden Informationen stellen ein unverbindliches Informationsangebot dar und beziehen sich auf die Prüfungsordnung MSBWL/13, SMPO 6. Änderungsordnung (zum WS 2018/19) (08.02.2019) für den Studiengang Master Betriebswirtschaftslehre. Rechtlich verbindliche Informationen entnehmen Sie bitte der offiziellen Veröffentlichung der Prüfungsordnung.

Modulinhalt

Begriff des Approximationsalgorithmus und der Approximierbarkeit; Schwerpunkt: Approximations-algorithmen, die auf linearer Optimierung basieren: LP-Runden; Dual Fitting; Primal-Duales Schema; Semidefinite Relaxationen; Iteriertes Runden; Approximationsschemata; Approximationsalgorithmen für Netzwerk Design; Facility Location; u.ä. Es wird an die aktuelle Forschung herangeführt.

Lernziele

Die Studierenden erwerben Fertigkeiten zu Entwurf und Analyse von polynomialen Algorithmen zur Approximation schwerer kombinatorischer Optimierungsprobleme. Sie können insbesondere ihre Kenntnisse aus der linearen Optimierung einsetzen, um die Güte von Approximationsalgorithmen zu analysieren. Die Studierenden sollen ein Verständnis des Stoffs entwickeln, das ihnen erlaubt, aktuelle und einschlägige Veröffentlichungen auf dem Gebiet der Approximationsalgorithmen einordnen und verstehen zu können.

Voraussetzungen

mindestens OR1 und/oder Grundkenntnisse in linearer Optimierung/Dualität; Grundkenntnisse in algorithmischer diskreter Mathematik (Graphen, Graphenalgorithmen, Analyse/Komplexität von Algorithmen); Grundkenntnisse von Problemen der diskreten Optimierung/Operations Research (Knapsack, Matching, Set Cover, Bin Packing, TSP, etc.) sehr hilfreich; mathematische Grundfertigkeiten unverzichtbar.

Prüfungsleistung

Klausur (100%, benotet, 90min.) oder Mündliche Prüfung (100%, benotet, 30min.)

Sonstige Informationen

Unregelmäßiges Angebot im Winter

Literatur

Zur Zeit keine Angaben auf Deutsch verfügbar.