Neuer Algorithmus: Dualvorhersagen beschleunigen Minimum‑Cost‑Flow um 12,7×

In einer kürzlich veröffentlichten Studie auf arXiv wird gezeigt, dass maschinell erstellte Vorhersagen klassische Algorithmen signifikant beschleunigen können. Der vorgestellte Ansatz ist der erste Minimum‑Cost‑Flow‑Algorithmus, der eine Dualvorhersage nutzt.

Der Kern des Verfahrens ist die bekannte ε‑Relaxation‑Methode, die nun um eine Vorhersage des Dualwertes erweitert wird. Die Autoren liefern Zeitkomplexitätsgrenzen, die sich direkt aus dem Fehler der Vorhersage im Unendlichen‑Normmaß ableiten lassen – ein Ansatz, der sowohl konsistent als auch robust ist.

Zusätzlich werden Sample‑Komplexitätsgrenzen für das PAC‑Lernen der Vorhersage hergeleitet. Die theoretischen Ergebnisse werden in zwei praktischen Anwendungen getestet: Verkehrsnetzwerken und Chip‑Escape‑Routing. Für die Verkehrsnetzwerke wird eine feste Vorhersage gelernt, während für das Routing ein auf Merkmalen basierendes neuronales Netzwerk eingesetzt wird.

Die Experimente zeigen beeindruckende Geschwindigkeitssteigerungen: durchschnittlich 12,74‑fach bei Verkehrsnetzwerken und 1,64‑fach bei Chip‑Routing. Diese Ergebnisse unterstreichen das Potenzial von Dualvorhersagen, klassische Netzwerkflussalgorithmen deutlich zu beschleunigen.