Doorbraak: ETH Zurich-onderzoekers ontwikkelen supersnel algoritme voor netwerken, zetten nieuwe snelheidsrecords

AmsterdamOnderzoekers van ETH Zürich, onder leiding van Rasmus Kyng, hebben de snelste algoritme ontwikkeld voor het oplossen van netwerkstroomproblemen. Deze nieuwe methode zal naar verwachting de manier waarop we optimale stromen in netwerken berekenen aanzienlijk veranderen.

Kyng's algoritme biedt een oplossing voor het maximale stroomprobleem. Het bepaalt de meest efficiënte manier om goederen door een netwerk te vervoeren met minimale kosten. Deze methode kan worden toegepast op verschillende soorten netwerken, zoals transportsystemen en het internet.

Belangrijke punten over het nieuwe algoritme:

• Berekenen van optimale netwerkstromen bijna direct na het inlezen van de data
• Geschikt voor zowel statische als dynamisch veranderende netwerken
• Beheert zowel de toevoeging als verwijdering van netwerkverbindingen
• Aangemerkt als een van de tien grootste ontdekkingen in de informatica van 2022
• Winnaar van de Best Paper Award 2022 op het IEEE Annual Symposium on Foundations of Computer Science (FOCS)

In het verleden kostte het veel tijd om de beste routes in netwerken te vinden. Naarmate netwerken groter en complexer werden, nam de tijd om deze te berekenen nog verder toe. Maar met Kyng's methode gaan de benodigde berekeningstijd en de grootte van het netwerk gelijk op.

Tot 2004 konden de beste algoritmes netwerkstromen berekenen met een tijdcomplexiteit evenredig aan het aantal verbindingen tot de macht van 1,5. In 2004 werd dit verbeterd naar een tijdcomplexiteit evenredig aan het aantal verbindingen tot de macht van 1,33. Inmiddels verlaagt Kyng's algoritme de benodigde rekentijd aanzienlijk.

Kyng's werk wordt verbeterd. De geüpdatete algoritmes werken nu voor netwerken die in de tijd veranderen. Ze berekenen snel de beste doorstromingen, zelfs in netwerken met veel wijzigingen. Dit is van belang voor praktische netwerken zoals verkeerssystemen die constant veranderen.

Simon Meierhans van ETH presenteerde tijdens het ACM Symposium on Theory of Computing in Vancouver een supersnel algoritme. Dit algoritme tackleert het minimumkosten maximumstroom probleem voor netwerken die geleidelijk veranderen.

Lees ook:

Vandaag · 13:52

Doorbraak in behandeling van hartritmestoornissen ontdekt

Het team heeft een nieuwe studie gepubliceerd die geaccepteerd is door FOCS, waarin ze een algoritme hebben ontwikkeld om het verwijderen van verbindingen te beheren. Dit is nuttig bij gebeurtenissen zoals het sluiten en heropenen van verkeersroutes.

Het team van Kyng ontwikkelde een vernieuwende methode door bestaande technieken te verfijnen. In plaats van met grote delen te werken, gebruiken ze veel kleine stappen. Hierdoor worden de berekeningen aanzienlijk sneller uitgevoerd.

In de jaren vijftig begonnen onderzoekers systematisch stroomproblemen in netwerken op te lossen. Tijdens deze periode ontwikkelden Lester R. Ford Jr. en Delbert R. Fulkerson belangrijke algoritmen. Zij richtten zich op het maximum-flowprobleem, waarbij goederen efficiënt door een netwerk worden verplaatst.

De meeste eerdere algoritmes waren effectief maar traag. Het algoritme van Kyng is echter zowel effectief als snel. Voor Kyng richtten onderzoekers zich ofwel op het spoorwegmodel ofwel op het elektriciteitsnet. Kyng's methode combineert de beste aspecten van beide modellen.

Het team ontwikkelde nieuwe wiskundige hulpmiddelen om hun algoritmes sneller te laten werken. Ze vonden een nieuwe manier om netwerkgegevens te ordenen, wat helpt om veranderingen in netwerkverbindingen snel op te merken. Dit zorgt ervoor dat het algoritme veel sneller functioneert.

Onderzoekers van de ETH Zürich hebben nieuwe, razendsnelle algoritmen ontwikkeld. Deze algoritmen lossen grote problemen snel op en vernieuwen de manier waarop computers complexe taken uitvoeren.

Dit onderzoek is van groot belang in de informatica. Het verbetert de manier waarop we grote en dynamische netwerken van data verwerken. De toepassingen zijn veelzijdig en omvatten onder andere biologie en sociale netwerken.