Vi presenterar asymptotiskt snabbare approximationsalgoritmer för de generaliserade flödesproblem där multiplikatorer på kanter är högst 1. För denna förlust version av den maximala generaliserade flödet problem, vi får en additiv approximation av den maximala flödet i tiden e " m 3/2 log(U/ ) 2 ", Där m är antalet kanter i grafen, alla kapaciteter är heltal i intervallet {1,.., U }, och alla förlust multiplikatorer är förhållandet mellan heltal i detta intervall. För minsta kostnad förlust generaliserade flöde med kostnader i intervallet {1,.., U }, vi får ett flöde som har värde inom en tillsats av det maximala värdet och kostnad på mest den optimala kostnaden. I många parameterintervall, dessa algoritmer förbättras över de tidigare snabbaste algoritmer för den generaliserade maximal flödesproblem genom en faktor på m 1/2 och för den minsta kostnaden generaliserade flödesproblem genom en faktor på ungefär m 1/2 / 2. Algoritmerna arbetar genom att accelerera traditionella inre punktalgoritmer genom att snabbt lösa systemet med linjära ekvationer som uppstår i varje steg. Bidragen från detta dokument är tvåfaldiga. Först analyserar vi prestandan hos inre punktalgoritmer med ungefärliga linjära systemlösare. Denna analys ensam ger en algoritm för den standard minsta kostnadsflöde problem som körs i tid "över tidigare algoritmer. För det andra undersöker vi de linjära ekvationer som uppstår när man använder en inre punktalgoritm för att lösa generella flödesproblem. Vi observerar att dessa tillhör familjen av symmetriska M-matriser, och vi utvecklar sedan e O (m)-tid al- * Detta material bygger på arbete som stöds av National Science Foundation under Grant Nos. CCF-0707522 och CCF-0634957. Alla åsikter, resultat och slutsatser eller rekommendationer som uttrycks i detta material är upphovsmännens och återspeglar inte nödvändigtvis den nationella vetenskapsstiftelsens åsikter. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Gorithms för att lösa linjära system i dessa matriser. Dessa algoritmer minskar problemet med att lösa ett linjärt system i en symmetrisk M -matris till att lösa O (log n) linjära system i symmetrisk diagonalt dominerande matriser, som vi kan göra i tid e O (m) med hjälp av algoritmen Spielman och Teng. Alla våra algoritmer fungerar på antal bitlängd som mest O (log nU/ ).
I kombination med minsta kostnadsflödesalgoritm från REF gav dessa algoritmer en drifttid på O(m 1,5 poly(k, −1 )).
Faster approximate lossy generalized flow via interior point algorithms
{'venue': "STOC '08", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}