Neuer Algorithmus der ETH Zürich beschleunigt Netzwerkfluss-Berechnungen und stellt Geschwindigkeitsrekorde auf

BerlinWissenschaftler der ETH Zürich unter der Leitung von Rasmus Kyng haben den weltweit schnellsten Algorithmus zur Lösung von Netzwerkflussproblemen entwickelt. Diese neue Methode könnte die Berechnung optimaler Flüsse in Netzwerken revolutionieren.

Der Kyng-Algorithmus löst das Maximalfluss-Problem. Er findet den effizientesten Weg, Güter durch ein Netzwerk zu bewegen und dabei die Kosten niedrig zu halten. Diese Methode lässt sich auf verschiedene Netzwerke anwenden, wie zum Beispiel Transportsysteme und das Internet.

Hier sind die wichtigsten Aspekte des neuen Algorithmus:

Revolutionäre Entdeckung in der Netzwerkanalyse

• Berechnet nahezu augenblicklich den optimalen Netzwerkfluss nach Dateneingabe
• Funktioniert für statische und sich schrittweise ändernde Netzwerke
• Verarbeitet sowohl das Hinzufügen als auch das Entfernen von Netzwerkverbindungen
• Gehört zu den zehn größten Entdeckungen in der Informatik des Jahres 2022
• Gewann den Best Paper Award 2022 auf dem IEEE Annual Symposium on Foundations of Computer Science (FOCS)

Früher nahm die Suche nach den besten Routen in Netzwerken viel Zeit in Anspruch. Mit wachsender Größe und Komplexität der Netzwerke stieg auch der Zeitaufwand für deren Berechnung. Doch dank der Kyng-Methode steigen der benötigte Zeitaufwand und die Netzwerkgröße nun im gleichen Verhältnis.

Bis 2004 konnten die besten Algorithmen den Fluss in einem Netzwerk mit einer Zeitkomplexität berechnen, die proportional zur Anzahl der Verbindungen hoch 1,5 war. Im Jahr 2004 gelang es, diese Komplexität auf eine Zeit proportional zur Anzahl der Verbindungen hoch 1,33 zu reduzieren. Nun senkt Kyngs Algorithmus die zusätzliche Rechenzeit noch einmal erheblich.

Die Arbeit von Kyng wird verbessert. Die aktualisierten Algorithmen funktionieren jetzt auch für Netzwerke, die sich im Laufe der Zeit verändern. Sie berechnen die optimalen Flüsse schnell, selbst in Netzwerken mit vielen Veränderungen. Dies ist besonders wichtig für reale Netzwerke wie Verkehrssysteme, die ständig in Bewegung sind.

Simon Meierhans von der ETH präsentierte auf dem ACM Symposium für Theoretische Informatik in Vancouver einen herausragenden schnellen Algorithmus. Dieser Algorithmus löst das Problem der minimalen Kosten für maximalen Fluss in Netzwerken, die sich schrittweise ändern.

Lesen Sie auch:

Heute · 13:52

Durchbruch bei Herzrhythmusstörungen: Neue Behandlungswege entdeckt

Das Team veröffentlichte ein weiteres Papier, das von der FOCS akzeptiert wurde, in dem sie einen Algorithmus entwickelten, um das Entfernen von Verbindungen zu verwalten. Dies erleichtert den Umgang mit realen Situationen wie dem Schließen und Wiederöffnen von Verkehrswegen.

Kyngs Team hat eine neue Methode entwickelt, indem es ältere Techniken verbesserte. Anstatt mit großen Abschnitten zu arbeiten, nutzen sie viele kleine Schritte. Diese Vorgehensweise macht die Berechnungen deutlich schneller.

In den 1950er Jahren begannen Forscher systematisch Flussprobleme in Netzwerken zu lösen. In dieser Zeit entwickelten Lester R. Ford Jr. und Delbert R. Fulkerson wichtige Algorithmen. Sie beschäftigten sich mit dem Maximalflussproblem, bei dem es darum geht, Güter effizient durch ein Netzwerk zu transportieren.

Die meisten früheren Algorithmen waren effektiv, aber langsam. Kyngs Algorithmus hingegen ist sowohl effektiv als auch schnell. Vor Kyng konzentrierten sich die Forscher entweder auf das Modell der Eisenbahnnetze oder der Stromnetze. Kyngs Methode vereint die besten Aspekte beider Ansätze.

Das Team entwickelte neue mathematische Werkzeuge, um ihre Algorithmen schneller zu machen. Sie fanden eine neue Methode, um Netzwerkdaten zu organisieren, was hilft, Veränderungen in den Netzwerkverbindungen rasch zu erkennen. Dadurch wird der Algorithmus erheblich schneller.

Wissenschaftler der ETH Zürich haben hochschnelle neue Algorithmen entwickelt. Diese Algorithmen lösen große Probleme im Handumdrehen und revolutionieren die Art und Weise, wie Computer komplexe Aufgaben bewältigen.

Diese Forschung ist bedeutend für die Informatik. Sie verbessert die Verwaltung großer und dynamischer Datennetzwerke. Anwendbar ist sie in verschiedenen Bereichen wie der Biologie und sozialen Netzwerken.