Forschungsinstitut für Diskrete Mathematik

Hauptseminar Diskrete Optimierung

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:

  1. Tim Roughgarden: Selfish Routing and the Price of Anarchy. MIT Press, 2005
  2. 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
Es wird vorausgesetzt, daß alle Teilnehmerinnen und Teilnehmer Kapitel 1 des Buches von Roughgarden vor Beginn des Seminars gelesen haben.



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