ETH-Informatiker schreiben schnellstmöglichen Fluss-Algorithmus

Rasmus Kyng und seinem Team an der ETH ist ein Durchbruch gelungen, an dem seit 90 Jahren geforscht wurde: Ihr Netzwerkfluss-Algorithmus berechnet den optimalen und kostengünstigsten Verkehrsfluss, und zwar für jede Art von Netzwerk, egal, ob Schiene, Strasse, Wasser oder Internet. Und vor allem tut er das so schnell, dass er in dem selben Moment, in dem ein Computer die Daten gelesen hat, bereits die Lösung präsentiert.

Wie die ETH in einem Bericht ausführt, schaffte es bis zur Jahrtausendwende kein Algorithmus, schneller zu rechnen als m^1,5, wobei m für die Anzahl Verbindungen in einem Netz steht, die der Computer berechnen muss. Ab 2004 gelang es, die zur Problemlösung benötigte Rechenzeit auf m^1,33 zu senken. Mit dem Algorithmus von Kyng ist nun die zusätzliche erforderliche Rechenzeit so gut wie auf null gesunken.

Kyngs Doktorvater Daniel A. Spielman, als Mathematik- und Informatikprofessor an der amerikanischen Eliteuniversität Yale selbst ein Pionier auf diesem Gebiet, bezeichnete diesen bahnbrechenden Algorithmus als „absurd schnell“. Mittlerweile haben die Forschenden ihren Ansatz den Angaben zufolge verfeinert und weitere fast-linearzeitliche Algorithmen entwickelt.

Der neueste Algorithmus wurde am 27. Juni am Annual ACM Symposium on Theory of Computing vorgestellt. Dieser löst das Minimum-Cost-Maximum-Flow-Problem auch für Netzwerke, die sich schrittweise verändern, indem neue Verbindungen dazukommen. In einem zweiten Paper, das das IEEE Symposium on Foundations of Computer Science vom nächsten Oktober angenommen hat, stellen die ETH-Forscher zudem einen weiteren Algorithmus vor, der auch das Entfernen von Verbindungen berücksichtigt. ce/mm