‚Absurd schneller‘ Algorithmus für den Netzwerkdurchfluss

Ein Team von Informatikern hat einen wesentlich schnelleren Algorithmus für eines der ältesten Probleme der Informatik entwickelt: den maximalen Fluss. [...]

Foto: Wikpedia.org, George Flonkerton, Creative Commons

Beim Maximum flow Problem geht es um die Frage, wie viel Material durch ein Netz von einer Quelle zu einem Ziel fließen 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ößten 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.

*Bernhard Lauer ist unter anderem freier Redakteur der dotnetpro und betreut hier beispielsweise die Rubrik Basic Instinct. Mit Visual Basic programmiert er privat seit der Version 1.0.


Mehr Artikel

Die beiden Sprecherinnen von Women@DSAG: (links) Franziska Niebauer, Beraterin für SAP IS-H bei der Helios Kliniken GmbH, und Anna Hartmann, Geschäftsführerin der in4MD Service GmbH (c) Bild links: Helios Kliniken GmbH; Bild rechts: www.AndreasLander.de
News

Chancengleichheit der Geschlechter – überbewertet oder wichtiger denn je?

In den USA schaffen Großkonzerne auf Geheiß Donald Trumps ihre Diversitätsprogramme ab. Auch in Europa folgen Unternehmen dem „Anti-Woke-Kurs“. Die DSAG nahm dies zum Anlass, bei den Mitgliedern des Frauennetzwerks Women@DSAG nachzufragen, wie es derzeit um die Chancengleichheit der Geschlechter im Job steht. 139 Frauen aus Deutschland, Österreich und der Schweiz nahmen an der Umfrage teil. […]

"Sammlung allerhand auserlesener Reponsorum […]", Johann Hieronymus Hermann, 1736 (c) Österreichische Nationalbibliothek
News

Kulturpool – digitalisiertes Kulturerbe

Einer der Vorteile der Digitalisierung ist, dass Kulturgüter zunehmend auch in digitalisierter Version für alle online zugänglich vorliegen. So versammelt das zentrale Suchportal für digitalisiertes Kulturerbe in Österreich, Kulturpool, 1,6 Millionen Objekten, darunter historische Handschriften, Bücher, Kunstwerke und vieles mehr. Einer der Hauptbeiträger von Kulturpool ist die Österreichische Nationalbibliothek. […]

Be the first to comment

Leave a Reply

Your email address will not be published.


*