Kombinatorische Optimierung (WiSe 2018/2019)

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)

Folien

Hier können Sie im Laufe des Semesters die LaTeX-Folien herunter laden, die ich in der Vorlesung verwende:

Nach jeder Vorlesung stelle ich hier den in der Vorlesung erzeugten handschriftlichen Teil (ersetzt einen Tafelanschrieb) zur Verfügung:

Übungsblätter

Hier können Sie im Laufe des Semesters die Übungsblätter herunter laden.

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