Kombinatorische Optimierung (WiSe 2020/2021)

Inhalt

Das Thema dieser Vorlesung aus dem Bereich der Diskreten Optimierung sind Probleme, die über kombinatorische Strukturen z.B. in Graphen oder Netzwerken formuliert sind. Die Vorlesung stellt im ersten (größeren) Teil die "Juwelen der kombinatorischen Optimierung" vor, nämlich die wichtigsten polynomial lösbaren Kernprobleme, wobei Algorithmen und polyedrische Strukturresultate eng verwoben sind (Matchings, Bäume/ Matroide, Flüsse, Wege).

Im zweiten (kleineren) Teil werden Konzepte und Methoden für NP-schwere kombinatorische Optimierungsprobleme an ausgewählten Beispielproblemen vermittelt (Approximationsalgorithmen, Heuristiken, Branch-and-Bound, duale Schranken, partielle polyedrische Beschreibungen). Während für die eleganten Resultate im ersten Teil die Theorie der linearen Optimierung verantwortlich ist, kommt im zweiten Teil ein größeres Spektrum der mathematischen Optimierungsmethodik zum Einsatz (u.a semidefinite Optimierung).

Termine

Vorlesung (Prof. V. Kaibel); Eintrag im LSF Übung (Jonas Frede); Eintrag im LSF

(Campus-Plan)

Material für die Vorlesungen und Übungen

Aufgrund der aktuellen Lage haben wir uns dazu entschlossen, den Kurs online zu halten und alle erforderlichen Materialien über Moodle anzubieten. Bitte entnehmen Sie den Link zur Moodle-Kursseite aus dem LSF oder hier: Link zum Moodle-Kurs.

Prüfung / Leistungsnachweis / Bachelorarbeit

Für die Prüfung empfehlen wir Ihnen, sich neben dem Vorlesungsstoff mit allen Übungsblättern ausgiebig zu beschäftigen.

Kriterien zur Vergabe eines Leistungsnachweises (nicht nötig im Studiengang B.Sc. Mathematik) werden am Anfang des Semesters bekannt gegeben.

Von denjenigen Studierenden, die Interesse an einer Bachelorarbeit in der Arbeitsgruppe haben, erwarten wir ebenfalls, dass die für den Leistungsnachweis nötigen Voraussetzungen erfüllt werden.

Literatur