'Absurd schneller' Algorithmus für den Netzwerkdurchfluss

Beim Maximum flow Problem geht es um die Frage, wie viel Material durch ein Netz von einer Quelle zu einem Ziel fliessen kann, wenn die Verbindungen im Netz Kapazitätsgrenzen haben. Der neue Algorithmus ist "absurd schnell", so Daniel Spielman von der Universität Yale. "Ich war eigentlich geneigt zu glauben, dass [...] so gute Algorithmen für dieses Problem nicht existieren würden".

Der maximale Fluss wird seit den 1950er Jahren erforscht, als er zur Untersuchung des sowjetischen Eisenbahnsystems formuliert wurde. Das Problem hat viele Anwendungen: Datenfluss im Internet, Flugplanung und sogar die Zuordnung von Bewerbern zu offenen Stellen. Das neue Papier behandelt sowohl den maximalen Datenfluss als auch eine allgemeinere Version des Problems, bei der man auch die Kosten minimieren möchte. Im Laufe der Jahre haben diese beiden Probleme viele der grössten Fortschritte bei algorithmischen Techniken inspiriert.

Der neue Algorithmus löst diese beiden Probleme in "fast linearer" Zeit, was bedeutet, dass die Laufzeit des Algorithmus ungefähr proportional zu der Zeit ist, die man braucht, um die Details des Netzwerks überhaupt erst einmal aufzuschreiben. Kein anderer Algorithmus für diese Probleme läuft auch nur annähernd so schnell.

Weitere Informationen dazu finden Sie im englischsprachigen Artikel von Erica Klarreich auf dieser Seite.