‚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

David Blum, Defense & Security Lead bei Accenture, im Gespräch mit der ITWELT.at. (c) timeline / Rudi Handl
Interview

„Ein resilientes Unternehmen zeichnet sich durch größtmögliche Transparenz aus“

Transparenz, soweit im Sicherheitskontext möglich, ist für David Blum, Defense & Security Lead bei Accenture, ein wichtiger Bestandteil von Unternehmensresilienz. Das fördere die aus dem Verständnis folgende Unterstützung der Mitarbeitenden. Die unternehmerische Resilienz müsse nicht nur technisch, sondern auch kulturell verankert werden: „Denn Resilienz beginnt im Kopf jedes Einzelnen“, sagt Blum im Gespräch mit der ITWELT.at. […]

News

Klassifizierung von KI-Systemen gemäß EU AI Act

Unternehmen, die KI nutzen, sollten die rechtlichen Rahmenbedingungen kennen, um teure Bußgelder zu vermeiden. Der EU AI Act stellt den ersten umfassenden Rechtsrahmen zur Regulierung von KI dar und zielt darauf ab, die Grundrechte der Bürger innerhalb der Europäischen Union zu schützen. Da der EU AI Act KI-Systeme nach Risikostufen klassifiziert und damit spezifische rechtliche Verpflichtungen beinhaltet, ist es für Unternehmen unerlässlich, ihre Systeme korrekt zu kategorisieren. […]

Nicola Acutt, Chief Sustainability Officer (CSO) von NetApp. (c) Wolfgang Franz
News

Nachhaltigkeit heißt Teamarbeit

Nicola Acutt ist der erste Chief Sustainability Officer (CSO) von NetApp. Im Gespräch mit transform! berichtet sie über die Herausforderungen und Chancen ihrer Rolle – und was ihre Leidenschaft fürs Segeln mit nachhaltiger Unternehmensführung gemeinsam hat. […]

Be the first to comment

Leave a Reply

Your email address will not be published.


*