Abstrakt. I det här dokumentet introducerar vi ett nytt ramverk för att i stort sett lösa flödesproblem i kapaciterade, oriktade grafer och tillämpa det för att ge asymptotiskt snabbare algoritmer för maximalt s-t-flöde och maximala samtidiga flödesproblem. För grafer med n hörn och m kanter, det gör att vi kan hitta en ε-ungefärlig maximal s-t flöde i tid O(m 1+o(1) ε −2 ), förbättra på den tidigare bästa gränsen av O(mn 1/3 poly(1/ε)). Att tillämpa samma ramverk i multicommodity-inställningen löser ett maximalt samtidigt multicommodityflödesproblem med k Våra algoritmer använder flera nya tekniska verktyg som vi tror kan vara av oberoende intresse: • Vi ger en icke-Euklidisk generalisering av lutning nedstigning och ger gränser på dess prestanda. Med hjälp av detta visar vi hur man kan minska ungefärligt maximalt flöde och maximalt samtidigt flöde till oöverträffad routing. • Vi definierar och tillhandahåller en effektiv konstruktion av en ny typ av flödessnålare. Tidigare sparfirkonstruktioner bevarade ungefär storleken på snitten och, genom dualitet, även värdet av de maximala flödena. De gav dock inte någon direkt väg till flödet i glesare G tillbaka i den ursprungliga grafen G, vilket ledde till ett långvarigt gap mellan effekten av sparifiering på flödet och skär problem. Vi lindrar detta genom att bygga en glesare G som kan inbäddas (mycket effektivt) i G med låg trängsel, vilket gör att man kan överföra flöden från G tillbaka till G. • Vi ger den första nästan linjära tiden konstruktion av en O (m o(1) )-konkurrensen ogenomförbara routing system. Ingen tidigare sådan algoritm kördes i tid bättre än  ska (mn). Genom att minska körtiden till nästan linjär ger vårt arbete en kraftfull ny primitiv för att konstruera mycket snabba grafalgoritmer. Vi noterar också att oberoende Jonah Sherman producerade en nästan linjär tid algoritm för maximalt flöde och vi tackar honom för att samordna bidrag.
Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. REF kombinerar Madry's idéer med ∞ optimeringsmetoder för att erhålla (1 − )-uppskattningar till maximalt flöde i m 1+o(1) −O(1) tid.
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}