Ny algoritm kan dramatiskt effektivisera lösningar på 'Max Flow'-problemet

Att hitta det mest effektiva sättet att transportera föremål över ett nätverk som det amerikanska motorvägssystemet eller Internet är ett problem som har beskattat matematiker och datavetare i årtionden.

För att ta itu med problemet har forskare traditionellt använt en maximiflödesalgoritm, även känd som maxflöde, där ett nätverk representeras som en graf med en serie noder, så kallade hörn, och förbindande linjer mellan dem, kallade kanter.

Med tanke på att varje kant har en maximal kapacitet - precis som vägarna eller de fiberoptiska kablarna som används för att överföra information runt Internet - försöker sådana algoritmer hitta det mest effektiva sättet att skicka varor från en nod i grafen till en annan, utan att överskrida dessa begränsningar.

Men eftersom storleken på nätverk som Internet har växt exponentiellt, är det ofta oöverkomligt tidskrävande att lösa dessa problem med traditionella datortekniker, enligt Jonathan Kelner, docent i tillämpad matematik vid MIT och medlem av MIT:s Laboratoriet för datavetenskap och artificiell intelligens (CSAIL).

Så i en artikel som ska presenteras vid ACM-SIAM Symposium on Discrete Algorithms i Portland, Oregon, denna vecka kommer Kelner och hans kollega Lorenzo Orecchia, en lärare i tillämpad matematik, tillsammans med doktoranderna Yin Tat Lee och Aaron Sidford, att beskriva en ny teoretisk algoritm som dramatiskt kan minska antalet operationer som behövs för att lösa maxflödesproblemet, vilket gör det möjligt att tackla även enorma nätverk som Internet eller det mänskliga genomet.

BILD: CHRISTINE DANILOFF / MED

Det har nyligen skett en explosion i storleken på grafer som studeras, säger Kelner. Om du till exempel vill dirigera trafik på Internet, studera alla kopplingar på Facebook eller analysera genomisk data, kan du lätt få grafer med miljoner, miljarder eller till och med biljoner kanter.

Tidigare maxflödesalgoritmer har kommit till problemet en kant, eller väg, i taget, säger Kelner. Så till exempel, när man skickar objekt från nod A till nod B, skulle algoritmerna överföra en del av varorna längs en väg, tills de nådde sin maximala kapacitet, och sedan börja skicka några nedför nästa väg.

Många tidigare algoritmer, säger Kelner, skulle hitta en väg från punkt A till punkt B, skicka lite flöde längs den och sedan säga, 'Med tanke på vad jag redan har gjort, kan jag hitta en annan väg längs som jag kan skicka mer?' När man behöver skicka flöde samtidigt längs många olika vägar, leder detta till en inneboende begränsning av algoritmens hastighet.

Men 2011 utvecklade Kelner, CSAIL doktorand Aleksander Madry, matematik undergraduate Paul Christiano och kollegor vid Yale University och University of Southern California en teknik för att analysera alla vägar samtidigt.

Forskarna såg grafen som en samling elektriska motstånd och föreställde sig sedan att koppla ett batteri till nod A och en jord till nod B och låta strömmen flyta genom nätverket. Elektrisk ström väljer inte bara en väg, den kommer att skicka lite ström över varje motstånd i nätverket, säger Kelner. Så den undersöker hela grafen globalt och studerar många vägar samtidigt.

Detta gjorde det möjligt för den nya algoritmen att lösa maxflödesproblemet betydligt snabbare än tidigare försök.

Nu har MIT-teamet utvecklat en teknik för att minska löptiden ytterligare, vilket gör det möjligt att analysera även gigantiska nätverk, säger Kelner.

Till skillnad från tidigare algoritmer, som har sett alla vägar i en graf som lika, identifierar den nya tekniken de rutter som skapar en flaskhals inom nätverket. Teamets algoritm delar upp varje graf i kluster av väl sammankopplade noder, och vägarna mellan dem som skapar flaskhalsar, säger Kelner.

Vår algoritm räknar ut vilka delar av grafen som enkelt kan dirigera vad de behöver och vilka delar som är flaskhalsarna. Det gör att man kan fokusera på problemområdena och strukturen på hög nivå, istället för att lägga mycket tid på att fatta oviktiga beslut, vilket gör att man kan använda sin tid mycket mer effektivt, säger han.

Resultatet är en nästan linjär algoritm, säger Kelner, vilket betyder att den tid det tar att lösa ett problem är mycket nära att vara direkt proportionell mot antalet noder i nätverket. Så om antalet noder på grafen multipliceras med 10, skulle tiden multipliceras med något mycket nära 10, i motsats till att multipliceras med 100 eller 1 000, säger han. Det betyder att den skalar i princip så bra som man kan hoppas på med storleken på insatsen, säger han.

Shanghua Teng, professor i datavetenskap vid University of Southern California som inte var inblandad i den senaste uppsatsen, säger att det representerar ett stort genombrott inom grafalgoritmer och optimeringsprogram.

Detta papper, som är vinnaren av priset för bästa papper vid [ACM-SIAM]-konferensen, är ett resultat av ihållande ansträngningar från Kelner och hans kollegor för att tillämpa elektriska flöden för att designa effektiva grafalgoritmer, säger Teng. Tidningen innehåller en fantastisk mängd tekniska bidrag.

Dölj