Ny algoritme kan dramatisk strømline løsninger på 'Max Flow'-problemet

At finde den mest effektive måde at transportere genstande på tværs af et netværk som det amerikanske motorvejssystem eller internettet er et problem, som har beskattet matematikere og dataloger i årtier.

For at tackle problemet har forskere traditionelt brugt en maksimal-flow-algoritme, også kendt som max flow, hvor et netværk er repræsenteret som en graf med en række knudepunkter, kendt som toppunkter, og forbindende linjer mellem dem, kaldet kanter.

I betragtning af at hver kant har en maksimal kapacitet - ligesom vejene eller de fiberoptiske kabler, der bruges til at transmittere information rundt på internettet - forsøger sådanne algoritmer at finde den mest effektive måde at sende varer fra en knude i grafen til en anden uden at overskride disse begrænsninger.

Men da størrelsen af ​​netværk som internettet er vokset eksponentielt, er det ofte uoverkommeligt tidskrævende at løse disse problemer ved hjælp af traditionelle computerteknikker, ifølge Jonathan Kelner, lektor i anvendt matematik ved MIT og medlem af MIT's. Datalogi og kunstig intelligens laboratorium (CSAIL).

Så i et papir, der skal præsenteres på ACM-SIAM Symposium on Discrete Algorithms i Portland, Ore., i denne uge, vil Kelner og hans kollega Lorenzo Orecchia, en anvendt matematikinstruktør, sammen med kandidatstuderende Yin Tat Lee og Aaron Sidford beskrive en ny teoretisk algoritme, der dramatisk kan reducere antallet af operationer, der er nødvendige for at løse max-flow-problemet, hvilket gør det muligt at tackle selv enorme netværk som internettet eller det menneskelige genom.

BILLEDE: CHRISTINE DANILOFF / MED

Der har for nylig været en eksplosion i størrelsen af ​​grafer, der studeres, siger Kelner. Hvis du for eksempel ville dirigere trafik på internettet, studere alle forbindelserne på Facebook eller analysere genomiske data, kunne du nemt ende med grafer med millioner, milliarder eller endda billioner af kanter.

Tidligere max-flow-algoritmer er kommet til problemet én kant eller vej ad gangen, siger Kelner. Så for eksempel, når der sendes varer fra node A til node B, ville algoritmerne transmittere nogle af varerne ned ad en vej, indtil de nåede dens maksimale kapacitet, og derefter begynde at sende nogle ned ad den næste vej.

Mange tidligere algoritmer, siger Kelner, ville finde en sti fra punkt A til punkt B, sende noget flow langs den og derefter sige: 'I betragtning af, hvad jeg allerede har gjort, kan jeg finde en anden sti, som jeg kan sende mere ad?' Når man skal sende flow samtidigt ad mange forskellige stier, fører dette til en iboende begrænsning af algoritmens hastighed.

Men i 2011 udviklede Kelner, CSAIL-kandidatstuderende Aleksander Madry, matematikundergraduat Paul Christiano og kolleger ved Yale University og University of Southern California en teknik til at analysere alle stierne samtidigt.

Forskerne så grafen som en samling af elektriske modstande og forestillede sig derefter at forbinde et batteri til node A og en jord til node B og lade strømmen strømme gennem netværket. Elektrisk strøm vælger ikke kun én vej, den vil sende en lille smule strøm over hver modstand på netværket, siger Kelner. Så den sonderer hele grafen globalt og studerer mange stier på samme tid.

Dette gjorde det muligt for den nye algoritme at løse max-flow-problemet væsentligt hurtigere end tidligere forsøg.

Nu har MIT-teamet udviklet en teknik til at reducere driftstiden endnu mere, hvilket gør det muligt at analysere selv gigantiske netværk, siger Kelner.

I modsætning til tidligere algoritmer, som har set alle stierne i en graf som ens, identificerer den nye teknik de ruter, der skaber en flaskehals i netværket. Holdets algoritme opdeler hver graf i klynger af godt forbundne noder, og stierne mellem dem, der skaber flaskehalse, siger Kelner.

Vores algoritme finder ud af, hvilke dele af grafen, der nemt kan rute, hvad de skal, og hvilke dele der er flaskehalsene. Det giver dig mulighed for at fokusere på problemområderne og strukturen på højt niveau i stedet for at bruge meget tid på at tage uvæsentlige beslutninger, hvilket betyder, at du kan bruge din tid meget mere effektivt, siger han.

Resultatet er en næsten lineær algoritme, siger Kelner, hvilket betyder, at den tid, det tager at løse et problem, er meget tæt på at være direkte proportional med antallet af noder på netværket. Så hvis antallet af noder på grafen ganges med 10, ville tidsmængden blive ganget med noget meget tæt på 10, i modsætning til at blive ganget med 100 eller 1.000, siger han. Det betyder, at det stort set skalerer så godt, som man kunne håbe på med størrelsen af ​​input, siger han.

Shanghua Teng, professor i datalogi ved University of Southern California, som ikke var involveret i det seneste papir, siger, at det repræsenterer et stort gennembrud inden for grafalgoritmer og optimeringssoftware.

Dette papir, som er vinderen af ​​prisen for bedste papir på [ACM-SIAM]-konferencen, er et resultat af vedvarende indsats fra Kelner og hans kolleger med at anvende elektriske strømme til at designe effektive grafalgoritmer, siger Teng. Papiret indeholder en fantastisk række tekniske bidrag.

skjule