Kombinatorische Optimierung (WiSe 2014/2015)

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

(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: Das 1. Übungsblatt wurde um eine Woche verschoben. Die Übung am 21.10. findet trotzdem statt!

Prüfung / Leistungsnachweis / Bachelorarbeit

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 Herrn Walter zu den Übungsaufgaben geben. Dazu sind eigene Aufzeichnungen zugelassen.

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