Angewandte Netzwerkoptimierung WS '01/'02

LV-Nr.: 0350 L 229

Aktuelle Hinweise

In der Woche vom 17. bis 21. Dezember sowie in der Woche vom 7. bis 11. Januar fällt die Vorlesung aus. Dafür gibt es voraussichtlich folgende Ersatztermine:

Freitag, 30. November, 12:15 bis 13:45 Uhr, MA 309
Freitag, 14. Dezember, 12:15 bis 13:45 Uhr, MA 309
Freitag, 18. Januar, 12:15 bis 13:45 Uhr, MA 309
Freitag, 1. Februar, 12:15 bis 13:45 Uhr, MA 309

Inhalt

Behandelt werden Netzwerkmodelle und Algorithmen, die in den Anwendungsbereichen Verkehrsleitung, Transport, Taktfahrpläne, Routenplanung von Bedeutung sind. Dies beinhaltet u.a. statische und dynamische Mehrgüterflussprobleme, längenbeschränkte Flüsse, gewichtete Zykelbasen graphischer Matroide und kürzeste Wege mit Nebenbedingungen. Die Veranstaltung ist als 3. Teil des Zyklus "Algorithmische Diskrete Mathematik" zulässig.

Mailingliste

Zur Ankündigung aller relevanter Informationen, die die Lehrveranstaltung betreffen, haben wir eine Mailingliste eingerichtet. Man kann sich dort selbst eintragen, indem man in das Formular auf der WWW-Seite http://www.math.TU-Berlin.de/cgi-bin/MajorUser seine Email-Adresse und den Namen der Liste netzwerkopt einträgt, auf den Find-Button klickt und danach "GO" anwählt. Danach erhält man die Liste angeboten. Nach "subscribe" wird man automatisch per Email aufgefordert, die Eintragung in die Liste zu bestätigen.

Voraussichtliche Termine

Di	16:05 - 17:35 Uhr	MA 371
Do	14:00 - 15:30 Uhr	MA 371

Sprechstunden

		Sprechstunde	Raum	Telefon	email
Dozent:	Martin Skutella	Di 10 - 11 Uhr	MA 603	314-25747	skutella@math.tu-berlin.de
Sekretariat:	Hannelore Vogt-Möller	Mo, Di, Do, Fr 9:30 - 11:30 Uhr	MA 601	314-25728	moeller@math.tu-berlin.de

Übungsblätter

Im Laufe des Semesters werden in unregelmäßigen Abständen Übungsblätter ausgegeben werden, die dann im Rahmen der Vorlesung besprochen werden bzw. von Teilnehmern der Vorlesung vorgerechnet werden sollen.

1. Übung [ Postscript, PDF ]
2. Übung [ Postscript, PDF ]
3. Übung [ Postscript, PDF ]
4. Übung [ Postscript, PDF ]
5. Übung [ Postscript, PDF ]
6. Übung [ Postscript, PDF ]
7. Übung [ Postscript, PDF ]
8. Übung [ Postscript, PDF ]
9. Übung [ Postscript, PDF ]

Literatur

Die folgende Literaturliste ist noch unvollständig und wird im Laufe des Semesters ergänzt werden.

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows - Theory, Algorithms, and Applications, Prentice Hall, Englewood Cliffs NJ, 1993.
(Standardlehrbuch im Bereich der Netzwerkflussalgorithmen - sehr ausführlich und umfassend)
D. Braess, Über ein Paradoxon aus der Verkehrsplanung, Unternehmensforschung 12, 258-268, 1969.
(Spezialliteratur - Originalpublikation zum Braess Paradoxon)
L. K. Fleischer and E. Tardos, Efficient continuous-time dynamic network flow algorithms, Operations Research Letters 23, 71-80, 1998.
(Fachartikel - Spezialliteratur) (*)
L. R. Ford and D. R. Fulkerson, Flows in networks, Princeton University Press, Princeton NJ, 1962.
(Altes aber dennoch lesenswertes Lehrbuch über Netzwerkflüsse)
M. R. Garey and D. S. Johnson, Computers and intractability: a guide to the theory of NP-completeness, Freeman, San Francisco, 1979.
(Lehrbuch über Komplexität - Liste von NP-vollständigen Problemen)
Grötschel, Lovasz, and Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer, Berlin, 1988. (Spezialliteratur - "Separieren=Optimieren")
B. E. Hoppe, Efficient dynamic network flow algorithms, Dissertation, Cornell University, 1995.
(Spezialliteratur) (*)
B. E. Hoppe and E. Tardos, Polynomial time algorithms for some evacuation problems, in Proceedings of the 5th Annual ACM--SIAM Symposium on Discrete Algorithms, 433-441, 1994.
(Spezialliteratur - bemerkenswert ist die Motivation zu Beginn der Einleitung: Anschlag auf das WTC 1993)
B. Klinz and G. J. Woeginger, Minimum cost dynamic flows: the series-parallel case, in E. Balas and J. Clausen (eds.), Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science 920, Springer, Berlin, 1995, 329-343.
(Spezialliteratur - Komplexitätsresultate für dynamische Flüsse) (*)
B. Korte and J. Vygen, Combinatorial Optimization - Theory and Algorithms, Springer, Berlin, 2000.
(Preisgünstiges Lehrbuch - sehr gut dazu geeignet, sich die für die Vorlesung nötigen Grundlagen der Kombinatorischen Optimierung anzueignen bzw. wieder ins Gedächtnis zu rufen)
T. Roughgarden and E. Tardos, How bad is selfish routing?, Journal of the ACM, to appear.
(Spezialliteratur zum Verhältnis von Nash Equilibrium und Systemoptimum)
A. Schrijver, On the history of the transportation and maximum flow problems, Mathematical Programming B, to appear.
(Interessantes zur Geschichte des MaxFlow Problems) (*)

Die mit einem (*) gekennzeichneten Einträge sind bei mir in elektronischer Form (ps-File oder pdf-File) erhältlich. Da ich sie aus Copyrightgründen nicht von dieser Seite aus verfügbar machen kann, schicke ich sie an Interessierte auf Anfrage per Email.

Last modified: Thu Jan 31 16:53:03 MET 2002

<skutella@math.tu-berlin.de>