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).
Achtung: Am 10. Januar findet keine der beiden Übungen statt!
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!
Achtung: Am 10. Januar findet keine Übung statt! Für das 11. Übungsblatt steht demzufolge mehr Zeit zur Verfügung.
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.