Wintersemester 2010/11
Thema: Verallgemeinerte Flußprobleme
Das Studium von Flußproblemen ist motiviert durch praktische Anwendungen, in denen Güter oder Personen beispielsweise in einem Straßen- oder Schienennetzwerk schnell und kostengünstig zu transportieren sind. Für viele solche Anwendungen sind die klassischen Max-Flow- oder Min-Cost-Flow-Probleme allerdings keine geeigneten Modellierungen, da sie nicht berücksichtigen, wie lange es dauert, eine Kante (die etwa einen Straßenabschnitt modelliert) zu durchlaufen. Diese Traversierungszeit kann natürlich auch von der aktuellen Auslastung der Kante abhängen. Außerdem kann z.B. der Automobilverkehr nur bedingt zentral gesteuert werden, so daß hier statt einer global optimalen Lösung eher Lösungen gefunden werden, in denen einzelne "Flußpartikel" (in diesem Fall also einzelne Autos) jeweils dem für sie günstigsten Weg folgen (selfish routing). Ein solche Lösung kann für alle Beteiligten sehr viel schlechter sein als eine global optimale Lösung.
In diesem Seminar werden wir untersuchen, wie sich diese Verallgemeinerungen auf die Flußprobleme auswirken und welche Fälle man noch effizient lösen kann. Grundlage der Vorträge werden Abschnitte aus einem Buch von Tim Roughgarden und einem Übersichtsartikel von Martin Skutella sein.
| Nr. | Probevortrag 12 Uhr c.t. |
Vortrag 14 Uhr c.t. |
Name | Thema | Betreuung |
|---|---|---|---|---|---|
| 1 | 27.9. | 11.10. | Berit Braun | Nash equilibria and optimal flows ([1], 2.1 -- 2.4) | Jan Schneider |
| 2 | 4.10. | 18.10. | Cyrill Berg | Existence and uniqueness of Nash flows ([1], 2.5 -- 2.7) | Jan Schneider |
| 3 | 4.10. (14 Uhr c.t.) |
25.10. | Rudolf Scheifele | The price of anarchy (I) ([1], 3.1 -- 3.3) | Ulrike Suhl |
| 4 | 18.10 | 8.11. | Anne-Marie George | The price of anarchy (II) ([1], 3.4 -- 3.5) | Ulrike Suhl |
| 5 | 25.10 | 15.11. | Thomas Weyd | The price of anarchy (III) ([1], 3.6 -- 4.1) | Christian Schulte |
| 6 | 8.11. | 22.11. | Lukas Oppenländer | Approximate Nash flows ([1], 4.2 -- 4.3) | Christian Schulte |
| 7 | 15.11. | 29.11. | Sebastian Sonntag | Atomic selfish routing ([1], 4.4 -- 4.5) | Jens Maßberg |
| 8 | 22.11. | 6.12. | Hilko Delonge | Better bounds ([1], 4.6 -- 4.7) | Jens Maßberg |
| 9 | 29.11. | 13.12. | Sonja Wittke | Bounding Braess's paradox ([1], 5.1 -- 5.2) | Christoph Bartoschek |
| 10 | 6.12. | 20.12. | Julia Schüller | Detecting Braess's paradox ([1], 5.3 -- 5.3.3) | Christoph Bartoschek |
| 11 | 13.12. | 10.1. | Jannik Silvanus | Braess's paradox and Stackelberg routing (I) ([1], 5.3.4 -- 6.3) | Dirk Müller |
| 12 | 20.12. | 17.1. | Theresa Kemper | Stackelberg routing ([1], 6.4 -- 6.6) | Markus Struzyna |
| 13 | 10.1. | 24.1. | Christiane Engels | Maximum Flows over time ([2], 21.1 -- 21.2) | Michael Gester |
| 14 | 17.1. | 31.1. | Clemens Rösner | Earliest arrival flows, Minimum-cost flows, and multicommodity flows over time ([2], 21.3 -- 21.5) | Michael Gester |
Literatur:
- Tim Roughgarden: Selfish Routing and the Price of Anarchy. MIT Press, 2005
- Martin Skutella: An Introduction to Network Flows over Time. In: William J. Cook, László Lovász, Jens Vygen (Herausgeber): Research Trends in Combinatorial Optimization. Springer-Verlag, 2009
- Von allen Teilnehmerinnen und Teilnehmern werden eine regelmäßige Teilnahme und eine aktive Mitarbeit erwartet.
- Die Vorträge sollen höchstens 75 Minuten dauern. Anschließend sind dann 15 Minuten für eine Diskussion vorgesehen.
- Alle Teilnehmerinnen und Teilnehmer müssen eine Zusammenfassung ihres Vortrags anfertigen, die mindestens eine und höchstens zwei Seiten lang ist.
- Alle Teilnehmerinnen und Teilnehmer müssen außerdem einen Probevortrag halten, der zwei bis drei Wochen vor dem eigentlichen Vortrag statfindet. Ein erfolgreicher Probevortrag ist Voraussetzung für den Vortrag im Seminar.
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Jun.Prof. Dr. T. Nieberg,
Jun.Prof. Dr. S. Held,
Dr. U. Brenner