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: