Banbrytande algoritm revolutionerar nätverksflödesoptimering snabbare och sänker transportkostnader i ny studie

StockholmRasmus Kyng och hans forskarteam har gjort ett betydande framsteg inom nätverksflödesalgoritmer. De har skapat en ny algoritm som hittar det mest effektiva sättet att transportera saker genom ett nätverk mycket snabbare än tidigare. Denna upptäckt kan påverka många områden, inklusive transporter, internettrafik och nätverk inom biologi.

Kyngs teams nya algoritm minskar transportkostnader och ökar nätverksflödet. Den analyserar snabbt nätverksdata och beräknar det optimala flödet. Detta är en betydande förbättring eftersom äldre algoritmer tog mycket längre tid att bearbeta ju större nätverket blev.

Därför är detta revolutionerande:

• Algoritmen ger lösningar direkt när en dator läser nätverksdata.
• Beräkningstiden och nätverkets storlek ökar i samma takt.
• Den överträffar tidigare algoritmer avsevärt.

Tidigare tog det lång tid att hitta det bästa flödet i stora nätverk. Kyng löste detta problem genom att göra processen snabb och effektiv. Den nya metoden innefattar många små, snabba beräkningar istället för några få stora. Denna förändring gör att det går mycket fortare.

I början av 2000-talet tog de snabbaste algoritmerna ungefär m^1.5 tid, där m är antalet nätverksförbindelser. År 2004 hade denna tid reducerats till m^1.33. Kyngs nya algoritm minskar nu den extra beräkningstiden nästan till noll, vilket gör den till den snabbaste algoritmen för dessa problem.

Läs också:

Idag · 02:08

Historisk fosteravård gav makt åt fattiga kvinnor

Kyngs team förbättrade sina metoder och utvecklade algoritmer som nästan omedelbart kan anpassa sig till föränderliga nätverk. Dessa algoritmer kan hantera nätverk med nya eller saknade kopplingar. Simon Meierhans, en medlem i teamet, presenterade en ny algoritm för inkrementella förändringar vid det årliga ACM-symposiet om teori inom datavetenskap i Vancouver. Denna algoritm kan uppdatera sig för nya kopplingar nästan omedelbart.

En ny studie som godkändes av FOCS i oktober presenterade en algoritm för att hantera nya och borttagna anslutningar. Detta möjliggör snabba och effektiva justeringar av rutter, vilket är användbart i verkliga situationer som att hantera vägarbeten eller hitta alternativa vägar runt olyckor.

Kyngs snabba beräkningar erbjuder en ny metod för att hantera komplexa nätverk. Tidigare algoritmer antingen analyserade delar av nätverket eller hela nätverket med hjälp av genomsnittsvärden. Kyngs metod kombinerar dessa två strategier för att öka effektiviteten.

Nya matematiska verktyg har utvecklats för att göra dessa algoritmer snabbare. Ett av dessa verktyg är ett nytt sätt att snabbare organisera nätverksdata. Detta hjälper till att upptäcka nätverksförändringar snabbare och påskyndar beräkningarna.

Detta arbete har löst många gamla problem och förbättrat hur datorer hanterar komplicerade uppgifter. Det kan bidra till att göra system som transport, kommunikation och biologi mer effektiva. Detta kan leda till bättre och snabbare applikationer inom olika områden.