contents
|
. . . . | Fluß- und Matchingalgorithmen |
|
|
Fluß- und Matching-Algorithmen - WS 1999/2000
Dr. Matthias Müller-Hannemann
Termine
Achtung: Auf Wunsch der Hörerinnen und Hörer wurde der Freitagstermin auf
Donnerstag umgelegt. 
Sprechzeiten
Inhalt
Von Standardalgorithmen zu fortgeschrittenen Techniken aus der
aktuellen Forschung für die effiziente Lösung von Optimierungsproblemen
auf Netzwerken (z.B. maximale Flüsse, Flüsse minimaler Kosten, Kardinalitätsmatching, gewichtetes Matching, b-Matching, T-joins, bigerichtete Flüsse, Flüsse mit Multiplikatoren, ...);
Theorie und Praxis von Fluß- und Matchingalgorithmen
und ihre vielfältigen Anwendungen
Zwei Leitmotive:
1) Wie lassen sich Algorithmen schrittweise verbessern?
Hier werden wir exemplarisch die spannenden historischen Entwicklungslinien
nachvollziehen, entlang derer algorithmische Fortschritte erzielt wurden,
bis hin zu kürzlich erzielten neuen Durchbrüchen.
2) Wie gut sind die Algorithmen in der Praxis? Und wie bekommt man dies heraus?
Dazu behandeln wir Aspekte der Implementation, des Testens und der
praktischen Analyse von Algorithmen.
Literatur
Als Lektüre zur Vertiefung und Erweiterung des Vorlesungsstoffes
verweisen wir auf folgende Bücher:
- R.K. Ahuja, T.L. Magnanti, J.B. Orlin: "Network Flows: Theory,
Algorithms, and Applications", Prentice-Hall, 1993
- W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver:
"Combinatorial Optimization", Wiley, 1998
- L.R. Ford, D.R. Fulkerson: "Flows in Networks",
Princeton University Press, 1962
Wesentliche Teile der Vorlesung werden jedoch auf aktueller Literatur
in Fachzeitschriften beruhen.
Scheinkriterien
- regelmäßige Teilnahme und Mitarbeit in der Vorlesung
- Rücksprache am Semesterende oder
- Programmprojekt (``Implementation Challenge'')
|
top
