contents
. . . . | Algorithmen für Verkehrsnetze |
|
|
Algorithmen für Verkehrsnetze - WS 2003/2004
Ekkehard Köhler
Inhalt der Vorlesung
Schwerpunkte der Vorlesung sind algorithmische Fragestellungen, die insbesondere bei der Verkehrsplanung und -optimierung auftreten. So werden verschiedene kürzeste Wegeprobleme und entsprechende Algorithmen betrachtet, es werden Verkehrsumlegungsprobleme untersucht (User Equilibrium vs. System Optimum) und verschiedene Ansätze zur dynamischen Verkehrsplanung mittels dynamischer Netzwerkflüsse betrachtet.
Die Veranstaltung ist als 3. Teil des Zyklus "Algorithmische Diskrete
Mathematik" zulässig.
Termine
Vorlesungen: |
Dienstag |
14-16 Uhr |
MA 548 |
Donnerstag |
12-14 Uhr |
MA 548 |
Sprechzeiten
Literatur
Als Lektüre zur Vertiefung und Erweiterung des Vorlesungsstoffes
sei auf folgende Bücher verwiesen. Die Liste 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.
- L. R. Ford and D. R. Fulkerson, Flows in networks,
Princeton University Press, Princeton NJ, 1962.
- M. R. Garey and D. S. Johnson, Computers and intractability:
a guide to the theory of NP-completeness, Freeman, San Francisco,
1979.
- B. Korte and J. Vygen, Combinatorial Optimization -
Theory and Algorithms, Springer, Berlin, 2000.
- A. Schrijver, Combinatorial Optimization --- Polyhedra and Efficiency, Springer, Berlin, 2003.
- Folien zur Vorlesung zu k-splittable Flows (PDF)
- T. Roughgarden and É. Tardos, How bad is selfish Routing, Journal of the ACM, 49(2):236--259, März 2002.
- T. Roughgarden, Designing networks for selfish users is hard, manuscript.
- H. Lin, T. Roughgarden, and É. Tardos, A stronger bound on Braess's Paradox, SODA 2004, pages 333--334.
Darüber hinaus empfehlen wir jedem Teilnehmer der Vorlesung,
weitere Literatur per Datenbankrecherche zu suchen. Eine komfortable
Möglichkeit dazu bietet die MATH Database in Karlsruhe,
die über WWW verfügbar ist.
Übungsblätter
Im Laufe des Semesters werden an dieser Stelle Übungsblätter
zur Verfügung gestellt. Die Bearbeitungszeit
beträgt in der Regel eine Woche. Es erfolgt keine Abgabe der gerechneten Übungsblätter; stattdessen wird an ausgewählten Vorlesungsterminen die Möglichkeit gegeben, die Lösungen der Übungsaufgaben zu presentieren.
Hier sind die PS- bzw. PDF-Files der Übungsblätter:
Scheinkriterien
Aktive Teilnahme an der Lösung der Übungsaufgaben; Rücksprache am Ende des Semesters.
|