Manoj Gupta überwindet Hürde bei Kürzeste-Wege-Algorithmen von 1996

Manoj Gupta vom Indian Institute of Technology Gandhinagar hat einen Algorithmus entwickelt, der eine seit 1996 bestehende Beschränkung in der Informatik überwindet. Das Verfahren liefert genauere Näherungen für kürzeste Wege zwischen Punkten, die nahe beieinander liegen, und braucht dafür nicht mehr Rechenzeit.

Die Berechnung kürzester Wege gehört zum Alltag von Computern. Navigations-Apps, Verkehrssysteme und die Internetinfrastruktur nutzen sie. Deutlich anspruchsvoller wird die Aufgabe, wenn die Entfernungen zwischen allen möglichen Punktpaaren eines sehr großen Netzwerks bestimmt werden müssen. In der Informatik heißt dieses Problem All-Pairs Shortest Paths (APSP). Ein Netzwerk ist dabei eine Menge von Punkten, die durch Beziehungen verbunden sind – sie können Städte, Rechner, Bahnhöfe oder sogar Neuronen darstellen.

Die Schwäche des Verfahrens von 1996

Alle exakten Routen in einem großen, dicht vernetzten Graphen zu berechnen, erfordert enorme Ressourcen. Deshalb suchen Forschende seit Langem nach Methoden, die verlässliche Ergebnisse liefern, ohne jeden Pfad zu prüfen. 1996 stellten Dor, Halperin und Zwick einen Algorithmus vor, der garantiert, dass die Schätzung höchstens doppelt so groß ist wie der tatsächlich kürzeste Weg – eine 2-Approximation.

Die Garantie galt jedoch vor allem für weit entfernte Punkte. Bei kurzen Verbindungen konnten die Fehler größer ausfallen: Besteht die echte Route aus zwei Teilstücken, konnte die Schätzung fünf ergeben und damit den doppelten Spielraum überschreiten.

Guptas Ansatz

Gupta verbessert die Auswahl der Punkte, die zur Schätzung dienen. Der frühere Ansatz stützte sich auf eine relativ kleine Menge repräsentativer Knoten. Der neue Algorithmus nutzt dagegen mehrskaliges Sampling: Er betrachtet die Struktur des Netzwerks auf mehreren Ebenen statt nur mit einer einzigen Punktmenge.

So berücksichtigt die Methode auch kürzere Verbindungen, die zuvor durchs Raster fielen. Entscheidend ist, dass die höhere Genauigkeit die gesamte Rechenkomplexität nicht erhöht. Die Ergebnisse werden verlässlicher, ohne dass die Laufzeit steigt.

Relevant sein könnte das für Telekommunikation, Verkehr, soziale Medien und KI-Systeme. Überall dort helfen schnelle, verlässliche Distanzschätzungen, Abhängigkeiten zu analysieren und ganze Systeme zu optimieren.