‚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

News

Datenschutzverstöße in Österreich nehmen zu

2024 kam es in Europa zu 130.000 Datenschutzverstößen – davon rund 1.300 in Österreich. Für Österreich bedeutet das einen Anstieg der Datenschutzverstöß von 21 Prozent im Vergleich mit dem Jahr 2023. Nur 4 Länder verzeichneten Rückgänge bei den Verstößen. Seit dem DSGVO-Start wurden in der EU 5,9 Milliarden Euro Bußgelder verhängt. […]

News

Best Practices zum Umgang mit Lookalike-Domains

Bei Cyberangriffen, die Lookalike-Domains nutzen, registrieren Angreifer für sich Domains, die legitimen Domains echter Unternehmen sehr ähnlich sehen. Nachdem sie sich die entsprechende Domain gesichert haben, beginnen sie dann, die dazugehörigen E-Mail-Server für eine E-Mail-Angriffskampagne herzurichten. […]

Raiffeisen Bank International etabliert internationales FinTech-Scout-Netzwerk. (c) Unsplash
News

RBI setzt auf globale FinTech-Scouts

Die Raiffeisen Bank International (RBI) verstärkt ihre Bemühungen im Bereich Finanzinnovationen durch die Etablierung eines global verteilten Teams von FinTech-Scouts. Diese Experten sollen Marktentwicklungen und neue Geschäftsmodelle aufzeigen sowie direkten Zugang zu relevanten Technologieanbietern weltweit ermöglichen. […]

News

Hightech-Crime-Report: Advanced Persistent Threats setzen Europa unter Druck

Mit einem Anstieg von 22 Prozent gegenüber dem Vorjahr nahmen betrügerische Machenschaften 2024 weltweit zu. Europäische Finanzdienstleister waren mit 34 Prozent aller Betrugsfälle am stärksten betroffen, gefolgt von der Transportbranche und dem Regierungs- und Militärsektor. Auch bei Phishing-Angriffen setzte sich der Aufwärtstrend fort: Mehr als 80.000 Phishing-Websites wurden 2024 enttarnt – ein Anstieg um 22 Prozent gegenüber dem Vorjahr. […]

Be the first to comment

Leave a Reply

Your email address will not be published.


*