Department of Computer Science
Chair of Algorithm Engineering (Ls11)
Home Contact Deutsch English
menu-en
Seminar 041403 SoSe 2008: Flüsse in Netzwerken

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!

DatumVortragenderThemaBetreuer
18.6.'08Sylvie TemmeTwo-Commodity FlowProf. Mutzel
18.6.'08Björn BaumannFlow with Flow-Dependent Transit TimesKarsten Klein
25.6.'08Thorsten Humberg(Maximum Integer) Multiterminal FlowKarsten Klein
25.6.'08Nils Kriege(Maximum) Concurrent FlowMarkus Chimani
2.7.'08Martin GroßNowhere-Zero Flow / k-FlowKarsten Klein
2.7.'08Marcel PreußIntegral Flow with Homologous Arcs (=Integer Equal Flow)Markus Chimani
9.7.'08Moritz Schallaböck(Minimum) Unsplittable FlowMaria Kandyba
9.7.'08Sophia Kardungk-splittable FlowMaria Kandyba
9.7.'08Timon KelterGeneralized FlowMarkus Chimani
16.7.'08Matthias Woste(Length-Bounded) Disjoint PathsMaria Kandyba
16.7.'08Jan-Philipp KappmeierFlow on Hypergraphs (=Hyperflow)Markus Chimani

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

Imprint
<webmaster  ls11.cs.tu-dortmund.de>
The university does not accept liability for the contents of linked external internet sites