Algorithmen mit fast linearer Zeit für maximalen Fluss und Minimalkostenfluss

Das Maximum-Flow-Problem und seine Verallgemeinerung, das Minimum-Cost-Flow-Problem, sind klassische kombinatorische Graphenprobleme, die zahlreiche Anwendungen in der Technik und im wissenschaftlichen Rechnen finden. Das Highlight wird von einem technischen Kommentar des zweifachen Gödel-Preisträgers Prof. Shang-Hua Teng von der University of Southern California begleitet.

Das Paper "Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow" befasst sich mit der effizienten Berechnung von Maximum Flows und Minimum Cost Flows in Netzwerken. Bei diesen Problemen geht es um einen abstrakten Begriff des "Flusses" in einem Netzwerk, aber sie können zur Modellierung vieler Probleme in realen Netzwerken verwendet werden, z. B. bei der Lenkung des Verkehrs auf Strassen oder Zügen auf der Schiene, bei Waren in Versorgungsinfrastrukturen oder bei Daten in digitalen Netzwerken. Sogar das Problem der Identifizierung von Arbitragemöglichkeiten auf einem Handelsmarkt lässt sich mit Hilfe von Flussproblemen mit minimalen Kosten effektiv modellieren. Grob gesagt geht es bei Flussproblemen darum, so viele Einheiten des "Flusses" wie möglich in einem gegebenen Netz mit möglichst geringen Kosten zu transportieren. Beim Maximum-Flow-Problem geht es darum, den grösstmöglichen Durchfluss zwischen zwei Punkten im Netz zu finden, wenn Beschränkungen hinsichtlich der Durchflussmenge bestehen, die jede Netzverbindung bewältigen kann, während das Minimum-Cost-Flow-Problem zusätzlich die Minimierung der Transportkosten berücksichtigt.

Als mathematische Herausforderung war der heilige Gral der Flow-Forschung die Entwicklung von Flow-Algorithmen mit Laufzeiten, die nahezu linear mit der Grösse des Netzes skalieren. Dies wurde schliesslich durch den Algorithmus von Prof. Rasmus Kyng und Dr. Maximilian Probst Gutenberg und ihren Koautoren erreicht. Schnelle Laufzeiten sind besonders wichtig für den effizienten Umgang mit grossen und komplexen Netzwerken. Solche Algorithmen könnten die Effizienz bei der Lösung von Netzwerkoptimierungsproblemen erheblich verbessern, insbesondere in Anwendungen wie Logistik, Telekommunikation und Verkehrsplanung. Eine nahezu lineare Laufzeit würde es ermöglichen, Echtzeitanwendungen und komplexe Optimierungsaufgaben in großen Netzen effektiver zu bewältigen. Bislang sind die von Prof. Kyng, Dr. Probst Gutenberg und ihren Mitautoren vorgestellten neuen Algorithmen noch nicht praxistauglich, da sie auf einer theoretischen Analyse der Algorithmenleistung in Netzwerken beruhen, die größer sind als alles, was selbst Riesenunternehmen wie Google jemals in Betracht ziehen würden. Aber jetzt geht es darum, den Algorithmus zu vereinfachen und zu verbessern, damit er in der Praxis gut funktioniert.

Mit dem neuen Algorithmus ist es endlich gelungen, die Laufzeit von Algorithmen für Flussprobleme zu klären, die von Informatikern und und Mathematikern seit den 1930er Jahren, wenn nicht schon früher, untersucht wurden, also noch vor der Etablierung der Informatik als wissenschaftliche Disziplin. Der Algorithmus führt einen radikal neuen Ansatz für Strömungsprobleme ein, indem er einen Algorithmus entwirft, der die kontinuierliche Optimierung nahtlos mit leistungsstarken neuen Datenstrukturen für die Abschätzung von Entfernungen und die Entdeckung "lokaler" Wege zur Verbesserung einer Lösung verbindet und dabei eine auffallend neue Perspektive auf die durch ein Netzwerk induzierte Geometrie einnimmt.