Kombinatorische Optimierung (WiSe 2012/2013)

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 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 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 (M. Walter); Eintrag im LSF

Achtung: Am 10. Januar findet keine der beiden Übungen statt!

(Campus-Plan)

Folien

Hier können Sie die Folien herunter laden, die ich in der Vorlesung an manchen Stellen als Ergänzung zum Tafelvortrag benutze. Die Sammlung wird während des Semesters laufend aktualisiert. Achtung: Die Folien geben auf keinen Fall einen hinreichenden Überblick über die behandelten Themen!

Übungsblätter

Achtung: Am 10. Januar findet keine Übung statt! Für das 11. Übungsblatt steht demzufolge mehr Zeit zur Verfügung.

Prüfung / Leistungsnachweis

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

Für den Leistungsnachweis müssen Sie mindestens dreimal an der Tafel eine Übungsaufgabe vorgerechnet haben. Zudem wird es am Ende des Semesters ein Scheingespräch mit Prof. Kaibel zu den Übungsaufgaben geben. Dazu sind eigene Aufzeichnungen zugelassen.

Literatur