Netzwerkflüsse gehören zu den grundlegenden Modellen in den Anwendungen der Diskreten Mathematik, wie beispielsweise Anwendungen im Bereich B ("Verkehrs- und Telekommunikationsnetzwerke") des DFG-Forschungszentrums Matheon. In diesem Projekt untersuchten wir den möglichen Einfluss des Zufalls sowohl auf das Design als auch auf die (Laufzeit-)Analyse von Netzwerkalgorithmen. Unsere Ziele bezüglich des Entwurfs von Algorithmen waren randomisierte Algorithmen zur Berechnung kostenminimaler Flüsse, randomisierte Pivotregeln für den Simplex-Algorithmus, sowie Approximationsalgorithmen für schwere Optimierungsprobleme aus dem Komplex der zeitabhängigen Flüsse.
Bezüglich der Analyse von Algorithmen lag der Schwerpunkt auf der Anwendung der Smoothed Analysis, welche von Spielman und Teng entwickelt wurde, auf Netzwerkalgorithmen.

• DFG-Forschungszentrum Matheon "Mathematik für Schlüsseltechnologien",
  Projekt C6: Online-Reopt
• Bernd Gärtner (ETH Zürich) und Micha Sharir (Tel Aviv University)