A New Approach to the Maximum-Flow Problem.ppt

anewapproachtothemaximum flowproblem andrewv goldberg roberte tarjanpresentedbyandrewguillory outline backgrounddefinitionspush relabelalgorithmcorrectness terminationproofssequentialimplementationdynamictreeimplementation maximumflowproblem classicprobleminoperationsresearchmanyproblemsreducetomaxflowmaximumcardinalitybipartitematchingmaximumnumberofedgedisjointpathsminimumcut max flowmin cuttheorem machinelearningapplicationsstructuredprediction dualextragradientandbregmanprojections taskar lacoste julien jordanjmlr2006 localsearchforbalancedsubmodularclusterings narasimhan bilmes ijcai2007 relationtooptimization specialcaseofsubmodularfunctionminimizationspecialcaseoflinearprogrammingintegeredgecapacitiespermitintegermaximumflows constructiveproof historyofalgorithms augmentingpathsbasedalgorithmsford fulkerson 1962 o mu edmonds karp 1969 o nm3 o n3 o nmlog n o nmlog u push relabelbasedalgorithmsgoldberg 1985 o n3 goldbergandtarjan 1986 o nmlog n2 m ahujaandorlino nm n2log u outline backgrounddefinitionspush relabelalgorithmcorrectness terminationproofssequentialimplementationdynamictreeimplementation definitions graphg v e v n e mgisaflownetworkifithassourcesandsinktcapacityc v w foreachedge v w inec v w 0for v w notine definitions continued aflowfongisarealvaluefunctiononvertexpairsf v w c v w forall v w f v w f w v uf u v 0forallvinv s t valueofaflow f is vf v t maximumflowisaflowofmaximumvalue definitions continuedagain apreflowfongisarealvaluefunctiononvertexpairsf v w 0forallvinv s flowexcesse v uf u v intuition flowintoavertexcanexceedflowout outline backgrounddefinitionspush relabelalgorithmcorrectness terminationproofssequentialimplementationdynamictreeimplementation intuition startingwithapreflow pushexcessflowclosertowardssinkifexcessflowcannotreachsink pushitbackwardstosourceeventually preflowbecomesaflowandinfactthemaximumflow residualgraph residualcapacityrf v w ofavertexpairisc v w f v w ifvhaspositiveexcessand v w hasresidualcapacity canpush min e v rf v w flowfromvtowedge v w issaturatedifrf v w 0residualgraphgf v ef whereefisthesetofresidualedges v w withrf v w 0 labeling avalidlabelingisafunctiondfromverticestononnegativeintegersd s nd t 0d v n d v nisalowerboundondistancetosource pushoperation push v w precondition visactive e v 0 andrf v w 0andd v d w 1action push min e v rf v w fromvtowf v w f v w f w v f w v e v e v e w e w relabeloperation relabel v precondition visactive e v 0 andrf v w 0impliesd v d w action d v min d w 1 v w inef genericpush relabelalgorithm startingfromaninitialpreflow whilethereisanactivevertexchoseanactivevertexvapplypush v w forsomeworrelabel v example 0 3 0 1 0 2 flownetwork s t example 4 0 0 0 3 3 0 1 0 2 s t initialpreflow labeling example 4 0 0 0 3 3 0 1 0 2 s t selectanactivevertex example 4 1 0 0 3 3 0 1 0 2 relabelactivevertex s t example 4 1 0 0 3 3 0 1 0 2 selectanactivevertex s t example 4 1 0 0 3 3 1 1 0 2 pushexcessfromactivevertex s t example 4 1 0 0 3 3 1 1 0 2 selectanactivevertex s t example 4 1 1 0 3 3 1 1 0 2 relabelactivevertex s t example 4 1 1 0 3 3 1 1 0 2 selectanactivevertex s t example 4 1 1 0 3 3 1 1 1 2 pushexcessfromactivevertex s t example 4 1 1 0 3 3 1 1 1 2 selectanactivevertex s t example 4 5 1 0 3 3 1 1 1 2 relabelactivevertex s t example 4 5 1 0 3 3 1 1 1 2 selectanactivevertex s t example 4 5 1 0 1 3 1 1 1 2 pushexcessfromvertex s t example 4 5 1 0 1 3 1 1 1 2 maximumflow s t outline backgrounddefinitionspush relabelalgorithmcorrectness terminationproofssequentialimplementationdynamictreeimplementation correctness lemma2 1iffisapreflow disavalidlabeling andvisactive eitherpushorrelabelisapplicabletovlemma3 1thealgorithmmaintainsavalidlabelingdtheorem3 2aflowismaximumiffthereisnopathfromstotingf fordandfulkerson 7 correctness continued lemma3 3iffisapreflowanddisavalidlabelingforf thereisnopathfromstotingfproofbycontradictionpaths v0 v1 vl timpliesthatd s d v0 1 d v1 2 d t l nwhichcontradictsd s n correctness continued theorem3 4ifthealgorithmterminateswithavalidlabeling thepreflowisamaximumflowifthealgorithmterminates allverticeshavezeroexcess preflowisaflow bylemma3 3thesinkisnotreachablefromthesourcebytheorem3 2theflowismaximum termination lemma3 5iffisapreflowandvisanactivevertexthenthesourceisreachablefromvingfletsbethesetofverticesreachableingfsupposesisnotinsforeveryu w withwinsandunotins f u w 0 winse w uinv winsf u w unotins winsf u w uins winsf u w unotins winsf u w 0e w 0forallwinslemma3 6avertex slabelneverdecreases termination continued lemma3 7atanytimethelabelofanyvertexisatmost2n 1onlyactivevertexlabelsarechangedactiveverticescanreachspathv v0 v1 vl simpliesthatd v d v0 1 d v1 2 d s l n n 1 termination continued lemma3 8thereareatmost2n2labelingoperationsonlythelabelscorrespondingtov s t mayberelabeledeachofthesen 2labelscanonlyincreaseatmost 2n 1 n 2 relabelings termination continued lemma3 9thenumberofsaturatingpushesisatmost2nmforanypair v w d w mustincreaseby2betweensaturatingpushesfromvtowsimilarlyd v mustincreaseby2betweenpushesfromwtovd v d w 1onthefirstsaturatingpushd v d w 4n 3onthelastatmost2n 1saturatingpushesperedge termination continued lemma3 10thenumberofnonsaturatingpushesisatmost4n2m vd v wherevisactiveeachnonsaturatingpushcauses todecreasebyatleast1thetotalincreasein fromsaturatingpushesis 2n 1 2nmthetotalincreasein fromrelabelingis 2n 1 n 2 is0initiallyand0attermination termination theorem3 11thealgorithmterminatesino n2m totaltime nonsaturatingpushes saturatingpushes relabelingoperations4n2m 2nm 2n2 o n2m outline backgrounddefinitionspush relabelalgorithmcorrectness terminationproofssequentialimplementationdynamictreeimplementation implementation ateachstepselectanactivevertexandapplyeitherpushorrelabelproblem determiningwhichoperationtoperformandinthecaseofpushfindingaresidualedgesolution foreachvertexmaintainalistofedgeswhichtouchthatvertexandacurrentedge push relabeloperation push relabel v precondition visactiveaction ifpush v w isapplicabletocurrentedge v w thenpush v w elseif v w isnotthelastedgeadvancecurrentedgeelseresetthecurrentedgeandrelabel v push relabeloperation lemma4 1thepush relabeloperationdoesarelabelingonlywhenrelabelingisapplicabletheorem4 2thepush relabelimplementationrunsino nm timepluso 1 timepernonsaturatingpushoperation o n3 bound wecanselectverticesinarbitraryordercertainvertexselectionstrategiesgiveo n3 boundsmaximumdistancemethod provedhere first in first outmethod provedinpaper wavemethod maximumdistancemethod ateachstep selecttheactivevertexwithmaximumdistanced v maximumdistancemethod theoremthemaximumdistancemethodperformsatmost4n3nonsaturatingpushesconsiderd maxxd x wherexisactivedonlyincreasesbecauseofrelabelingdincreasesatmost2n2timesdstartsat0andendsnonnegativedchangesatmost4n2timesthereisatmostonenonsaturatingpushpernodepervalueofd maximumdistancemethod theoremthemaximumdistancemethodrunsintimeo n3 usingthepush relabelimplementationprevioustheoremandtheorem4 2 first infirst outmethod discharge precondition queueisnotemptyaction push relabelthevertexvatthefrontofthequeueuntile v 0ord v increasesifwbecomesactiveduringthepush relabeladdwtothebackofthequeueifvisstillactiveaddvtothebackofthequeue first infirst outmethod lemma4 3thenumberofpassesoverthequeueisatmost4n2proofverysimilartotheproofofo n3 boundformaximumdistancemethodcorollary4 4thenumberofnonsaturatingpushesisatmost4n3onepervertexperpass first infirst outmethod theorem4 5thefirst in first outmethodrunsino n3 timecorollary4 4andtheorem4 2 outline backgrounddefinitionspush relabelalgorithmcorrectness terminationproofssequentialimplementationdynamictreeimplementation dynamictreeimplementation intuition maintaintreessuchthatconnectionsbetweenchildnodesandparentnodescorrespondtoedgesintheresidualgraphwhichpermitpushoperationssendflowupbranchesoftreesqueuecontainstreeswithactiveroots sendoperation send v precondition visactiveaction whilevisnottherootofitstreeande v 0sendflowupthetreefromvcutthetreealongthebottleneckedge s example 4 2 1 0 3 3 0 2 0 1 s t preflow labeling example 4 2 1 0 3 2 1 s t residualgraph excess 3 example 4 2 1 0 2 1 s t dynamictreeoverresidualgraph excess 3 example 4 2 1 0 2 1 s t selectactivevertex excess 3 example 4 2 1 0 1 0 s t sendflowuptree excess 2 example 4 2 1 0 1 s t cutalongbottleneckedges excess 2 example 4 2 1 0 0 s t sendflowuptree excess 1 example 4 2 1 0 s t cutalongbottleneckedges excess 1 excess 1 example 4 2 1 0 3 3 2 2 1 1 s t newpreflow labeling tree push relabeloperation tree push relabel v precondition visarootofatreeandactiveaction 1 ifpushisapplicabletocurrentedge v w 1a ifwecancombinevandw streeswithoutmakingthetree sizek makewv sparentandsend v 1b elsepush v w andsend w 2 else2a if v w isn tthelastedgeadvancetheedge2b elsecutv schildrenoutofthetree relabelv andresetthecurrentedge dynamictreeimplementation lemma5 1thedynamictreealgorithmrunsino nmlogk timepluso logk timeperadditionofavertextothequeuetreesarekeptatmostsizekby1a treeoperationstaketimeo logk eachtree push relabeloperationtakeso 1 treeoperationspluso 1 treeoperationspercutrelabelingtakestimeo nm thereareo nm cutstree push relabelisperformedo nm timesplusonceperadditiontothequeue dynamictreeimplementation lemma5 2thenumberoftimesavertexisaddedtothequeueiso nm n3 k avertexisaddedonlyafterd v changesore v increasesfromzerod v changesatmostn2timese v increasedonlyin1a or1b numberofverticesaddedtoqueuein1a or1b isthenumberofcutsperformed 2nm plusoneperoccurrenceofeachsubcase dynamictreeimp