- Das Forschungsteam von Rasmus Kyng an der ETH Zurich hat einen Algorithmus entwickelt, der Probleme der maximalen Flussmenge in Netzwerken und der Minimierung von Transportkosten nahezu an der mathematischen Geschwindigkeitsgrenze berechnet
- Der neue Algorithmus verfolgt einen Ansatz in nahezu linearer Zeit, bei dem die Antwort in fast derselben Größenordnung wie das Einlesen der Netzwerkdaten berechnet wird, und kann auf Netzwerke wie Eisenbahn, Straße, Wasserwege und Internet angewendet werden
- Früher lag die Laufzeit bei m Verbindungen bis zum Jahr 2000 bei m^1.5 und 2004 bei etwa m^1.33, doch Kyngs Ansatz senkt die zusätzliche Rechenzeit nach dem Einlesen der Daten auf ein vernachlässigbares Niveau
- Das Forschungsteam berechnet nicht nur in statischen, gerichteten Netzwerken, sondern auch in inkrementellen Graphen mit hinzugefügten Verbindungen und dekrementellen Graphen mit gelöschten Verbindungen kürzeste Wege und Maximum-Flow mit minimalen Kosten in nahezu linearer Zeit
- In Situationen, in denen sich reale Netzwerke verändern, etwa bei der Sperrung und teilweisen Wiedereröffnung des Gotthard-Basistunnels oder bei einem Erdrutsch auf der A13, schafft dies die Grundlage, optimale Routen schnell neu zu berechnen
Netzwerkflussprobleme nahezu an der Geschwindigkeitsgrenze berechnen
- Der Netzwerkfluss-Algorithmus des Forschungsteams um Rasmus Kyng behandelt das Problem, in einem Netzwerk den größtmöglichen Fluss zu finden und zugleich die Transportkosten zu minimieren
- Ein typisches Beispiel ist die Suche nach einer Route, auf der sich möglichst viele Güter von Copenhagen nach Milan so schnell und günstig wie möglich transportieren lassen
- In Netzwerken mit Verbindungen und Kapazitäten wie Eisenbahn, Straße, Wasserwegen oder dem Internet lässt sich so ein optimaler Fluss mit geringen Kosten berechnen
- Die Rechengeschwindigkeit wurde auf ein Niveau gesenkt, das fast der Zeit entspricht, die ein Computer zum Einlesen der Netzwerkdaten benötigt
Warum es der „schnellste“ Algorithmus ist
- Zuvor dauerte die Berechnung des optimalen Flusses deutlich länger als die Verarbeitung der Netzwerkdaten
- Je größer und komplexer ein Netzwerk wurde, desto schneller stieg die benötigte Rechenzeit im Verhältnis zur Problemgröße an
- Kyngs Ansatz sorgt dafür, dass Rechenzeit und Netzwerkgröße im gleichen Verhältnis wachsen
- Wenn die Anzahl der Netzwerkverbindungen m ist, braucht bereits das einmalige Einlesen der Daten m Zeit
- Bis zum Jahr 2000 gab es keinen Algorithmus, der schneller als m^1.5 rechnen konnte
- 2004 sank der nötige Rechenaufwand zur Problemlösung auf m^1.33
- Kyngs Algorithmus reduziert die zusätzliche Rechenzeit nach dem Einlesen der Daten bis zur Lösung auf ein vernachlässigbares Maß
Bewertung und Erweiterung des Algorithmus in nahezu linearer Zeit
- Das Team um Kyng veröffentlichte vor zwei Jahren eine Arbeit mit dem mathematischen Beweis dieses Konzepts
- Solche nahezu optimal schnellen Algorithmen werden als Algorithmen in nahezu linearer Zeit bezeichnet
- Daniel A. Spielman verglich den Algorithmus mit einem Porsche, der eine Pferdekutsche überholt
- Die Arbeit erhielt auf dem IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, den Best Paper Award
- Auch Communications of the ACM stellte die Forschung vor, und die Redaktion von Quanta wählte Kyngs Algorithmus zu einer der zehn wichtigsten Entdeckungen der Informatik im Jahr 2022
Von statischen zu sich verändernden Netzwerken
- Der ursprüngliche Algorithmus konzentrierte sich auf feste, statische Netzwerke mit vorgegebener Verbindungsrichtung
- Gerichtete Verbindungen entsprechen Strukturen wie Einbahnstraßen in einem städtischen Straßennetz
- Später entwickelte das Forschungsteam Algorithmen, die den optimalen Fluss auch in Netzwerken berechnen, die sich im Lauf der Zeit schrittweise verändern
- Simon Meierhans stellte auf dem Annual ACM Symposium on Theory of Computing, STOC, in Vancouver einen neuen Algorithmus in nahezu linearer Zeit vor
- Dieser Algorithmus löst das Minimum-Cost-Maximum-Flow-Problem in Netzwerken, in denen neue Verbindungen hinzukommen
- In einer zweiten Arbeit, die für das IEEE Symposium on Foundations of Computer Science, FOCS, im Oktober angenommen wurde, entwickelte das Team einen Algorithmus, der auch das Löschen von Verbindungen verarbeitet
- Beide Algorithmen identifizieren kürzeste Wege in Netzwerken, in denen Verbindungen hinzugefügt oder entfernt werden
Beispiele für Veränderungen in realen Netzwerken
- Der Gotthard-Basistunnel in Switzerland war seit dem Sommer 2023 vollständig gesperrt und wurde später teilweise wieder in Betrieb genommen
- Ein Teil der A13, einer wichtigen Alternativroute zum Gotthard-Strassentunnel, wurde kürzlich durch einen Erdrutsch zerstört
- Bei solchen Veränderungen müssen Computer, Online-Kartendienste und Routenplaner die kostengünstigste und kürzeste Verbindung zwischen Milan und Copenhagen neu berechnen
- Kyngs neuer Algorithmus berechnet optimale Routen auch in Netzwerken mit hinzugefügten oder gelöschten Verbindungen in nahezu linearer Zeit
- Auch wenn Umleitungen oder neue Strecken entstehen und dadurch Verbindungen hinzukommen, bleibt die zusätzliche Rechenzeit vernachlässigbar
Zwei bisherige Strategien und ihre neue Kombination
- Zur Berechnung von Netzwerkflüssen muss ein Netzwerk mehrfach analysiert werden, um optimalen Fluss und Wege mit minimalen Kosten zu finden
- In jeder Iteration werden Veränderungen geprüft, etwa welche Verbindungen offen oder geschlossen sind oder wo Kapazitätsgrenzen erreicht und Engpässe entstanden sind
- Vor Kyng nutzten Informatikerinnen und Informatiker hauptsächlich eine von zwei Strategien
- Eisenbahnnetz-Modell: In jeder Iteration wird ein ganzer Abschnitt eines Netzwerks berechnet, in dem sich der Verkehrsfluss verändert hat
- Stromnetz-Modell: In jeder Iteration wird das gesamte Netzwerk berechnet, wobei zur Beschleunigung statistische Mittelwerte für veränderte Flüsse in den einzelnen Abschnitten verwendet werden
- Das Forschungsteam um Kyng kombinierte die Vorteile beider Strategien zu einem neuen hybriden Ansatz
- Maximilian Probst Gutenberg geht davon aus, dass sich viele kleine, effiziente und kostengünstige Rechenschritte deutlich schneller kombinieren lassen als einige wenige große Schritte
Historischer Kontext von Flow-Algorithmen
- Das Netzwerkflussproblem war eines der frühen Probleme, die in den 1950er Jahren systematisch algorithmisch gelöst wurden
- Flow-Algorithmen spielten eine wichtige Rolle dabei, die theoretische Informatik als eigenständiges Forschungsfeld zu etablieren
- Auch der bekannte Algorithmus von Lester R. Ford Jr. und Delbert R. Fulkerson stammt aus dieser Zeit
- Der Ford-Fulkerson-Algorithmus löst effizient das Maximum-Flow-Problem, bei dem möglichst viele Güter durch ein Netzwerk transportiert werden sollen, ohne die Kapazität einzelner Wege zu überschreiten
- Spätere Forschung zeigte, dass das Maximum-Flow-Problem, das Minimum-Cost-Problem und mehrere weitere Netzwerkflussprobleme Spezialfälle des allgemeinen Minimum-Cost-Flow-Problems sind
Grenzen früherer Algorithmen und der Wendepunkt 2004
- Viele Algorithmen vor Kyngs Forschung konnten jeweils ein bestimmtes Problem effizient lösen, waren aber nicht schnell genug und ließen sich nur schwer auf das allgemeinere Minimum-Cost-Flow-Problem ausweiten
- John Edward Hopcroft, Richard Manning Karp und Robert Endre Tarjan, die in den 1970er Jahren wegweisende Flow-Algorithmen entwickelten, erhielten jeweils den Turing Award
- Karp erhielt die Auszeichnung 1985
- Hopcroft und Tarjan wurden 1986 ausgezeichnet
- 2004 entwickelten Daniel Spielman, Shang-Hua Teng und später Samuel Daitch Algorithmen, die auch für das Minimum-Cost-Flow-Problem schnelle und effiziente Lösungen boten
- Diese Gruppe verlagerte die Perspektive von der Eisenbahn auf den Stromfluss in Stromnetzen
- In Stromnetzen kann elektrischer Strom teilweise über Verbindungen umgeleitet werden, durch die bereits anderer Strom fließt
- Kyng übernahm nicht einfach Spielmans leistungsstarken Algorithmusansatz für das gesamte Netzwerk, sondern wandte die Idee der Berechnung partieller Pfade auf den früheren Ansatz von Hopcroft und Karp an
- Die Berechnung partieller Pfade in jeder Iteration trug entscheidend dazu bei, die gesamte Flussberechnung zu beschleunigen
Neue mathematische Werkzeuge und Datenstrukturen
- Der Fortschritt des ETH-Zurich-Teams beruht nicht nur auf neuen Algorithmen, sondern auch auf der Entwicklung mathematischer Werkzeuge, die Berechnungen beschleunigen
- Das Forschungsteam entwickelte neue Datenstrukturen zur Organisation von Netzwerkdaten
- Diese Datenstruktur ermöglicht es, Veränderungen an Netzwerkverbindungen sehr schnell zu identifizieren
- Die schnelle Erkennung von Änderungen erhöht die Geschwindigkeit der algorithmischen Lösung zusätzlich
- Algorithmen in nahezu linearer Zeit und die neuen Datenstrukturen schaffen eine Grundlage dafür, sehr große Probleme zu lösen, die zuvor nicht effizient berechnet werden konnten
Verwandte Arbeiten und Materialien
- Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality: FOCS-2024-Arbeit zu Minimum-Cost-Flow und mehr in dekrementellen Graphen
- Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow: STOC-2024-Arbeit zu Zykluserkennung, SCCs, s-t-kürzestem Weg und Minimum-Cost-Flow in inkrementellen Graphen
- Maximum Flow and Minimum-Cost Flow in Almost-Linear Time: FOCS-2022-Arbeit zu Maximum-Flow und Minimum-Cost-Flow in nahezu linearer Zeit
- Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow: einschlägiger Artikel in Communications of the ACM
- Researchers Achieve ‘Absurdly Fast’ Algorithm for Network Flow: zugehöriger Artikel aus dem Jahr 2022 in Quanta Magazine
1 Kommentare
Meinungen auf Hacker News
Dieser Algorithmus ist im Grenzfall n -> inf asymptotisch nahezu linear.
Am Ende des Videos heißt es, dass es für jede Implementierung dieses Algorithmus in der realen Welt schwierig sein dürfte, bestehende Algorithmen zu schlagen.
https://cacm.acm.org/research/almost-linear-time-algorithms-...
https://en.wikipedia.org/wiki/Galactic_algorithm
Die Formulierung schnellstmögliche Geschwindigkeit ist wirklich eine gewagte Behauptung.
In vielen Fällen ist es deutlich praktischer, mit 1 % der Zeit 99 % Qualität zu erreichen.
Interessanterweise arbeitet dieselbe Person auch daran, rein theoretische Algorithmen in der Praxis gut funktionieren zu lassen [1].
Allerdings scheint dieser Prozess dann noch einmal rund 20 Jahre zu dauern. [1] baut auf einem theoretischen Durchbruch von 2004 [2] auf, und nach meinem Verständnis begannen solche Algorithmen erst 2024, in der Praxis zu funktionieren. Demnach könnten wir wohl 2044 mit praktischen Minimum-Cost-Flow-Algorithmen rechnen.
[1] https://arxiv.org/pdf/2303.00709
[2] https://arxiv.org/abs/cs/0310051
Theoretisch ist es trotzdem ein schönes Ergebnis.
Manchmal habe ich das Gefühl, dass wir uns mit Komplexität als Kennzahl völlig verirrt haben.
Es gibt immer mehr Algorithmen, bei denen Komplexitätskennzahlen bis zum Wahnsinn optimiert wurden, die aber praktisch nicht nützlich sind.
Nachdem die einfachen Erfolge alle weg waren, wurde Algorithmik zu einem weiteren hochspezialisierten Feld, und wenn man nicht in einem sehr nah verwandten Bereich forscht, sind die meisten Papers den Zeitaufwand kaum wert.
Verwandte Beiträge: https://news.ycombinator.com/item?id=31149038 (40 Kommentare)
https://news.ycombinator.com/item?id=31675015 (72 Kommentare)
Wo findet man das Paper oder den Code?
https://cacm.acm.org/research/almost-linear-time-algorithms-...
Ich bin hier an einer Stelle verwirrt: o(n) scheint eine stärkere Aussage zu sein als O(n).
Denn jeder o(n)-Algorithmus ist O(n), aber nicht umgekehrt. Außerdem: Wenn o(n) auch für beliebig kleine n gilt und O(n) nur für n -> inf, müsste dieser Algorithmus dann nicht auch für kleine n anwendbar sein? Dann wäre er doch das Gegenteil des oben erwähnten galaktischen Algorithmus. Übersehe ich etwas?
Die Definition von f(n) = o(g(n)) lautet grob: lim (n -> infinity) f(n)/g(n) = 0. Mit anderen Worten: Für hinreichend große n wächst g schneller als f.
Zum Beispiel ist eine Funktion wie f(n) = 10n if n < 1000 else 1e1000 ein o(n). Denn wenn n wächst, geht 1e1000/n gegen 0. Das ist eine Pseudo-Python-Darstellung einer stückweise definierten Funktion, die bis n = 1000 exponentiell bis 101000 wächst und danach konstant bleibt.
Wenn ich mich richtig erinnere, ist 3↑↑64 Grahams Zahl.
Verdammt seien diese konstanten Faktoren, da schüttelt man die Faust gen Himmel.
Im Abstract steht nur, dass die Zeit m^(1+o(1)) beträgt.
Weiß jemand, ob irgendwo eine konkretere obere Schranke angegeben ist?
https://de.m.wikipedia.org/wiki/Landau-Symbole
Anders gesagt ist es ein Algorithmenschema, mit dem man für jedes beliebige ɛ>1 einen Algorithmus erhält, der in Zeit O(m^ɛ) läuft.
Das kleine o ist eine Funktion, die gegen 0 geht, wenn n gegen unendlich geht, und wird als asymptotisch vernachlässigbar bezeichnet.