Flüsse in Netzwerken

(Seminar 041403)

Sommersemester 2008

Prof. Dr. Petra Mutzel, Markus Chimani

Anmeldung und Vorbesprechung

Die Anmeldung, Vorbesprechung und Themenvergabe fand schon statt.
[Mi. 9. April 2008, 10:15 (erste Woche der Vorlesungszeit); Seminarraum 202, Otto-Hahn-Str. 14]

Termine

Diese Veranstaltung ist ein Seminar für Studierende im Hauptstudium. Zeitraum: Verlauf des Sommersemesters 2008.
Das Seminar findet jeweils Mittwochs, 10:00-12:00 Uhr (pünktlich), im Seminarraum 202 der Otto-Hahn-Str. 14 statt.
Achtung: am 9.7. beginnt das Seminar schon um 9:00 da wir 3 Vorträge erwarten!

Inhalt

Viele kombinatorische Optimierungsprobleme lassen sich als Flussprobleme modellieren, das heisst: gegeben ist ein Netzwerk mit bestimmten Kapazitätsbeschränkungen und gesucht ist ein Fluss durch dieses Netzwerk das bestimmte Anforderungen erfüllt. Einige Probleme dieser Klasse sind polynomiell lösbar, wie z.B. die bekannten Probleme Maximum-Flow oder Minimum-Cost-Flow. Viele Erweiterungen jedoch sind beweisbar NP-schwer, wie z.B. Multi-Commodity-Flow, diverse zeitabhängige Flussprobleme, etc.

In diesem Seminar betrachten wir die Vielfältigkeit der diversen Flussprobleme. Durch eine Mischung aus wichtigen Standardwerken und aktueller Literatur gewinnen wir einen Einblick in deren Komplexität und Approximierbarkeit, und lernen sowohl approximative als auch exakte Algorithmen zur Lösung dieser teilweise NP-schweren Probleme kennen.

Kenntnisse und Interesse in Graphenalgorithmen, linearer Optimierung und Algorithmentheorie sind erwünscht.

Ablauf des Seminars

Siehe die Introfolien.

Bitte beachtet dabei auch die Hinweise zur Foliengestaltung (pdf)!

Die schriftliche Ausarbeitung umfasst 15-20 Seiten und wird mit LaTeX erstellt. Die Abgabe der Ausarbeitung muss spätestens 4 Wochen vor dem jeweiligen Vortragstermin erfolgen.

Die erste Besprechung mit dem jeweiligen Betreuer findet spätestens 6 Wochen vor dem eigenen Vortragstermin statt. Zu diesem Zeitpunkt müssen die Vorträge noch nicht feinsäuberlich ausgearbeitet sein. Die bei der Vorbesprechung ausgegebene Literatur sollte jedoch gelesen worden sein und ein Grobkonzept des Vortrags und der Ausarbeitung sollte vorgestellt werden können. Natürlich dienen die Besprechungen auch dem Ausräumen von Unklarheiten und der Formulierung von Verständnisfragen.

Ansprechpartner

Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an:
markus . chimani (at) cs . uni-dortmund . de