Ny studie: Forskare skapar banbrytande flödesalgoritm som slår hastighetsrekord i nätverksberäkningar

StockholmForskare vid ETH Zürich, under ledning av Rasmus Kyng, har utvecklat den snabbaste algoritmen för att lösa nätverksflödesproblem. Denna nya metod förväntas förändra hur vi beräknar optimala flöden i nätverk.

Kyngs algoritm löser problemet med maximal flöde. Den hittar det mest effektiva sättet att transportera varor genom ett nätverk samtidigt som kostnaderna hålls nere. Denna metod kan användas för olika typer av nätverk, såsom transportsystem och internet.

Här är viktiga punkter om den nya algoritmen:

• Beräknar optimalt nätverksflöde nästan omedelbart efter att ha läst data
• Fungerar både för statiska och gradvis föränderliga nätverk
• Hanterar både tillägg och borttagning av nätverksförbindelser
• En av de tio största upptäckterna inom datavetenskap under 2022
• Vann priset för bästa artikel på IEEE:s årliga symposium om grundläggande datavetenskap (FOCS) 2022

Tidigare tog det mycket tid att hitta de bästa rutterna i nätverk. När nätverken blev större och mer komplexa ökade också tiden som krävdes för att beräkna dem. Men Kyngs metod garanterar att den tid som krävs för att beräkna och nätverkets storlek ökar i samma takt.

Fram till 2004 kunde de bästa algoritmerna beräkna flöden i ett nätverk med en tidskomplexitet proportionell mot antalet anslutningar upphöjt till 1,5. År 2004 förbättrades detta till en tidskomplexitet proportionell mot antalet anslutningar upphöjt till 1,33. Nu minskar Kyngs algoritm den extra beräkningstiden avsevärt.

Kyngs arbete förbättras nu. De uppdaterade algoritmerna fungerar nu även för nätverk som förändras över tid. De beräknar optimala flöden snabbt, även i nätverk med många förändringar. Detta är viktigt för verkliga nätverk som exempelvis trafiksystem som ständigt förändras.

Simon Meierhans från ETH presenterade en snabb algoritm på ACM Symposium on Theory of Computing i Vancouver. Algoritmen löser problemet med minimikostnad för maxflöde i nätverk som förändras lite i taget.

Läs också:

Idag · 15:52

Förbättra korallrevens hälsa genom vattenkvalitet i städerna

Teamet skrev en annan artikel som accepterades av FOCS där de utvecklade en algoritm för att hantera borttagning av förbindelser. Detta hjälper vid hantering av händelser i verkliga livet, såsom avstängning och återöppning av trafikvägar.

Kyngs team utvecklade en ny metod genom att förbättra tidigare tekniker. De använder många små steg istället för att arbeta med större sektioner. Detta tillvägagångssätt gör beräkningarna betydligt snabbare.

På 1950-talet började forskare systematiskt lösa flödesproblem i nätverk. Under denna period utvecklade Lester R. Ford Jr. och Delbert R. Fulkerson viktiga algoritmer. De tog sig an det så kallade maximiflödesproblemet, vilket handlar om att effektivt transportera varor genom ett nätverk.

De flesta tidigare algoritmer var effektiva men långsamma. Kyngs algoritm är både effektiv och snabb. Innan Kyng fokuserade forskare antingen på järnvägs- eller elnätsmodeller. Kyngs metod kombinerar de bästa aspekterna av båda modellerna.

Teamet utvecklade nya matematiska verktyg för att kunna göra sina algoritmer snabbare. De skapade ett nytt sätt att organisera nätverksdata som underlättar snabb upptäckt av förändringar i nätverksanslutningar. Detta gör algoritmen betydligt snabbare.

Forskare vid ETH Zürich har utvecklat nya algoritmer som arbetar mycket snabbt. Dessa algoritmer hjälper till att lösa stora problem snabbt och förändrar hur datorer hanterar svåra uppgifter.

Denna forskning är betydelsefull inom datavetenskap. Den förbättrar sättet vi hanterar stora och dynamiska datanätverk på. Forskningsresultaten kan tillämpas inom flera områden, såsom biologi och sociala nätverk.