RandomizationinGraphOptimizationProblems

《RandomizationinGraphOptimizationProblems》由会员分享，可在线阅读，更多相关《RandomizationinGraphOptimizationProblems（127页珍藏版）》请在装配图网上搜索。

1、MITRandomization in Graph Optimization ProblemsDavid KargerMIT1MITRandomized AlgorithmslFlip coins to decide what to do nextlAvoid hard work of making“right”choicelOften faster and simpler than deterministic algorithmslDifferent from average-case analysisInput is worst caseAlgorithm adds randomness2

2、MITMethodslRandom selectionif most candidate choices“good”,then a random choice is probably goodlRandom samplinggenerate a small random subproblemsolve,extrapolate to whole problemlMonte Carlo simulationsimulations estimate event likelihoodslRandomized Rounding for approximation3MITCuts in GraphslFo

3、cus on undirected graphslA cut is a vertex partitionlValue is number(or total weight)of crossing edges4MITOptimization with CutslCut values determine solution of many graph optimization problems:min-cut/max-flowmulticommodity flow(sort-of)bisection/separatornetwork reliabilitynetwork designRandomiza

4、tion helps solve these problems5MITPresentation AssumptionlFor entire presentation,we consider unweighted graphs(all edges have weight/capacity one)lAll results apply unchanged to arbitrarily weighted graphsInteger weights=parallel edgesRational weights scale to integersAnalysis unaffectedSome imple

5、mentation details6MITBasic ProbabilitylConditional probabilityPrA B=PrA PrB|AlIndependent events multiply:PrA B=PrA PrBlUnion BoundPrX Y PrX+PrYlLinearity of expectation:EX+Y=EX+EY7MITRandom Selection forMinimum CutsRandom choices are good when problems are rare8MITMinimum CutlSmallest cut of graphl

6、Cheapest way to separate into 2 partslVarious applications:network reliability(small cuts are weakest)subtour elimination constraints for TSPseparation oracle for network designlNot s-t min-cut9MITMax-flow/Min-cutls-t flow:edge-disjoint packing of s-t pathsls-t cut:a cut separating s and t lFF:s-t m

7、ax-flow=s-t min-cutmax-flow saturates all s-t min-cutsmost efficient way to find s-t min-cutslGH:min-cut is“all-pairs”s-t min-cutfind using n flow computations10MITFlow AlgorithmslPush-relabel GT:push“excess”around graph till its gonemax-flow in O*(mn)(note:O*hides logs)recent O*(m3/2)GRmin-cut in O

8、*(mn2)-“harder”than flowlPipelining HO:save push/relabel data between flowsmin-cut in O*(mn)-“as easy”as flow11MITContractionlFind edge that doesnt cross min-cutlContract(merge)endpoints to 1 vertex12MITContraction AlgorithmlRepeat n-2 times:find non-min-cut edgecontract it(keep parallel edges)lEach

9、 contraction decrements#verticeslAt end,2 vertices leftunique cutcorresponds to min-cut of starting graph1314MITPicking an EdgelMust contract non-min-cut edgeslNI:O(m)time algorithm to pick edgen contractions:O(mn)time for min-cutslightly faster than flowsIf only could find edge faster.Idea:min-cut

10、edges are few15MITRandomizeRepeat until 2 vertices remainpick a random edgecontract it(keep fingers crossed)16MITAnalysis IlMin-cut is small-few edgesSuppose graph has min-cut cThen minimum degree at least cThus at least nc/2 edgeslRandom edge is probably safePrmin-cut edge c/(nc/2)=2/n(easy general

11、ization to capacitated case)17MITAnalysis IIlAlgorithm succeeds if never accidentally contracts min-cut edgelContracts#vertices from n down to 2lWhen k vertices,chance of error is 2/kthus,chance of being right is 1-2/klPralways right is product of probabilities of being right each time18MITAnalysis

12、IIInot too good!19MITRepetitionlRepetition amplifies success probabilitybasic failure probability 1-2/n2so repeat 7n2 times20MITHow fast?lEasy to perform 1 trial in O(m)timejust use array of edges,no data structureslBut need n2 trials:O(mn2)timelSimpler than flows,but slower21MITAn improvement KSlWh

13、en k vertices,error probability 2/kbig when k smalllIdea:once k small,change algorithmalgorithm needs to be saferbut can afford to be slowerlAmplify by repetition!Repeat base algorithm many times22MITRecursive AlgorithmAlgorithm RCA(G,n)G has n vertices repeat twicerandomly contract G to n/2 vertice

14、sRCA(G,n/21/2)(50-50 chance of avoiding min-cut)23MITMain TheoremlOn any capacitated,undirected graph,Algorithm RCAruns in O*(n2)time with simple structuresfinds min-cut with probability 1/log nlThus,O(log n)repetitions suffice to find the minimum cut(failure probability 10-6)in O(n2 log2 n)time.24M

15、ITProof OutlinelGraph has O(n2)(capacitated)edgeslSo O(n2)work to contract,then two subproblems of size n/2T(n)=2 T(n/2)+O(n2)=O(n2 log n)lAlgorithm fails if both iterations failIteration succeeds if contractions and recursion succeedP(n)=1-1-P(n/2)2=W(1/log n)25MITFailure ModeslMonte Carlo algorith

16、ms always run fast and probably give you the right answerlLas Vegas algorithms probably run fast and always give you the right answerlTo make a Monte Carlo algorithm Las Vegas,need a way to check answerrepeat till answer is rightlNo fast min-cut check known(flow slow!)26MITHow do we verify a minimum

17、 cut?27MITEnumerating CutsThe probabilistic method,backwards28MITCut CountinglOriginal CA finds any given min-cut with probability at least 2/n(n-1)lOnly one cut foundlDisjoint events,so probabilities addlSo at most n(n-1)/2 min-cutsprobabilities would sum to more than onelTight Cycle has exactly th

18、is many min-cuts29MITEnumerationlRCA as stated has constant probability of finding any given min-cutlIf run O(log n)times,probability of missing a min-cut drops to 1/n3lBut only n2 min-cutslSo,probability miss any at most 1/nlSo,with probability 1-1/n,find allO(n2 log3 n)time30MITGeneralizationlIf G

19、 has min-cut c,cut ac is a-mincutlLemma:contraction algorithm finds any given a-mincut with probability W(n-2a)Proof:just add a factor to basic analysislCorollary:O(n2a)a-mincutslCorollary:Can find all in O*(n2a)time Just change contraction factor in RCA31MITSummarylA simple fast min-cut algorithmRa

20、ndom selection avoids rare problemslGeneralization to near-minimum cutslBound on number of small cutsProbabilistic method,backwards32MITRandom Sampling33MITRandom SamplinglGeneral tool for faster algorithms:pick a small,representative sampleanalyze it quickly(small)extrapolate to original(representa

21、tive)lSpeed-accuracy tradeoffsmaller sample means less timebut also less accuracy 34MITA Polling ProblemlPopulation of size mlSubset of c red memberslGoal:estimate clNave method:check whole populationlFaster method:samplingChoose random subset of populationUse relative frequency in sample as estimat

22、e for frequency in population35MITAnalysis:Chernoff BoundlRandom variables Xi 0,1lSum X=XilBound deviation from expectation Pr|X-EX|e EX exp(-e2EX/4)l“Probably,X (1e)EX”lIf EX 4(ln n)/e2,“tight concentration”Deviation by e probability 1/n36MITApplication to PollinglChoose each member with probabilit

23、y plLet X be total number of reds seenlThen EX=pclSo estimate by X/plNote accurate to within 1e iff X is within 1e of expectation:=X/p (1e)EX/p=(1e)c37MITAnalysislLet Xi=1 if ith red item chosen,else 0lThen X=XilChernoff Bound appliesPrdeviation by e exp(-e2pc/4)4(log n)/e2lPretty tightif pc 1Proble

24、m if only want single use of edgeslRound to approx,then fixSolve“augmentation problem”using other network design techniquesMay be worse approx,but only to a small part of cost69MITNonuniform SamplingConcentrate on the important thingsBenczur-Karger,Karger,Karger-Levine70MITs-t Min-CutslRecall:if G h

25、as min-cut c,then in G(r/c)all cuts approximate their expected values to within e.lApplications:Min-cut inO*(mc)time GApproximate/exact inO*(m/c)c)=O*(m)s-t min-cut of value v in O*(mv)Approximate inO*(mv/c)timelTrouble if c is small and v large.71MITThe ProblemlCut sampling relied on Chernoff bound

26、lChernoff bounds required that no one edge is a large fraction of the expectation of a cut it crosseslIf sample rate 1/c,each edge across a min-cut is too significantBut:if edge only crosses large cuts,then sample rate 1/c is OK!72MITBiased SamplinglOriginal sampling theorem weak whenlarge m small c

27、 lBut if m is largethen G has dense regionswhere c must be largewhere we can sample more sparsely73MITApprox.s-t min-cut O*(mv)O*(nv/e2)Approx.s-t min-cut O*(mn)O*(n2/e2)Approx.s-t max-flow O*(m3/2)O*(mn1/2/e)Flow of value v O*(mv)O*(nv)m n/e2 in weighted,undirected graphs Problem Old Time New Time7

28、4MITlDefinition:A k-strong component is a maximal vertex-induced subgraph with min-cut k.Strong Components223375MITNonuniform SamplinglDefinition:An edge is k-strong if its endpoints are in same k-component.lStricter than k-connected endpoints.lDefinition:The strong connectivity ce for edge e is the

29、 largest k for which e is k-strong.lPlan:sample dense regions lightly76MITNonuniform SamplinglIdea:if an edge is k-strong,then it is in a k-connected graphlSo“safe”to sample with probability 1/klProblem:if sample edges with different probabilities,Ecut value gets messylSolution:if sample e with prob

30、ability pe,give it weight 1/pelThen Ecut value=original cut value77MITCompression TheoremDefinition:Given compression probabilities pe,compressed graph Gpeincludes edge e with probability pe andgives it weight 1/pe if includedlNote EGpe=GTheorem:Gr/ce approximates all cuts by ehas O(rn)edges78MITApp

31、licationlCompress graph to rn=O*(n/e2)edgeslFind s-t max-flow in compressed graphlGives s-t mincut in compressedlSo approx.s-t mincut in originallAssorted runtimes:GT O(mn)becomes O*(n2/e2)FF O(mv)becomes O(nv/e2)GR O(m3/2)become O(n3/2/e3)79MITProof(approximation)lBasic idea:in a k-strong component

32、,edges get sampled with prob.r/koriginal sampling theorem workslProblem:some edges may be in stronger components,sampled lesslInduct up from strongest components:apply original sampling theorem insidethen“freeze”so dont affect weaker parts80MITStrength LemmalLemma:1/ce nConsider connected component

33、C of GSuppose C has min-cut kThen every edge e in C has ce kSo k edges crossing Cs min-cut have 1/ce 1/k k(1/k)=1Delete these edges(“cost”1)Repeat n-1 times:no more edges!81MITProof(edge count)lEdge e included with probability r/celSo expected number is S r/celWe saw S 1/ce nlSo expected number at m

34、ost r n82MITConstructionlTo sample,must find edge strengthscant,but approximation sufficeslSparse certificates identify weak edges:construct in linear time NIcontain all edges crossing cuts k iterate until strong components emergelIterate for 2i-strong edges,all itricks turn it strongly polynomial83

35、MITNI Certificate AlgorithmlRepeat k timesFind a spanning forestDelete itlEach iteration deletes one edge from every cut(forest is spanning)lSo at end,any edge crossing a cut of size k is deletedlNI pipeline all iterations in O(m)time84MITApproximate FlowslUniform sampling led to tree algorithmsRand

36、omly partition edgesMerge trees from each partition elementlCompression problematic for flowEdge capacities changedSo flow path capacities distortedFlow in compressed graph doesnt fit in original graph85MITSmoothinglIf edge has strength ce,divide into br/ce edges of capacity ce/brCreates br 1/ce =br

37、n edgeslNow each edge is only 1/br fraction of any cut of its strong componentlSo sampling a 1/b fraction workslSo dividing into b groups workslYields(1-e)max-flow in O*(mn1/2/e)time86MITExact Flow AlgorithmsSampling from residual graphs87MITResidual GraphslSampling can be used to approximate cuts a

38、nd flowslA non-maximum flow can be made maximum by augmenting pathslBut residual graph is directed.lCan sampling help?Yes,to a limited extent88MITFirst TrylSuppose current flow value fresidual flow value v-f lLemma:if all edges sampled with probability rv/c(v-f)then,w.h.p.,all directed cuts within e

39、 of expectationsOriginal undirected sampling used r/clExpectations nonzero,so no empty cutlSo,some augmenting path exists89MITApplicationlWhen residual flow i,seek augmenting path in a sample of mrv/ic edges.Time O(mrv/ic).lSum over all i from v down to 1lTotal O(mrv(log v)/c)since S1/i=O(log v)lHer

40、e,e can be any constant v/(v-f),then will find augmenting path w.h.p.lRuntime:a always within a factor of 2 of“right”v/(v-f)As in compression,edge count O(a r n)So runtime O(r n Siv/i)=O*(nv)94MITSummarylNonuniform sampling for cuts and flowslApproximate cuts in O(n2)timefor arbitrary flow valuelMax

41、 flow in O(nv)timeonly useful for“small”flow valuebut does work for weighted graphslarge flow open95MITNetwork ReliabilityMonte Carlo estimation96MITThe ProblemlInput:Graph G with n vertices Edge failure probabilitiesFor exposition,fix a single plOutput:FAIL(p):probability G is disconnected by edge

42、failures97MITApproximation AlgorithmslComputing FAIL(p)is#P complete VlExact algorithm seems unlikelylApproximation schemeGiven G,p,e,outputs e-approximationMay be randomized:succeed with high probabilityFully polynomial(FPRAS)if runtime is polynomial in n,1/e98MITMonte Carlo SimulationlFlip a coin

43、for each edge,test graphlk failures in t trials FAIL(p)k/tlEk/t=FAIL(p)lHow many trials needed for confidence?“bad luck”on trials can yield bad estimateclearly need at least 1/FAIL(p)lChernoff bound:O*(1/e2FAIL(p)suffice to give probable accuracy within eTime O*(m/e2FAIL(p)99MITChernoff BoundlRandom

44、 variables Xi 0,1lSum X=XilBound deviation from expectation Pr|X-EX|e EX exp(-e2EX/4)lIf EX 4(log n)/e2,“tight concentration”Deviation by e probability 1/nlNo one variable is a big part of EX 100MITApplicationlLet Xi=1 if trial i is a failure,else 0lLet X=X1+XtlThen EX=t FAIL(p)lChernoff says X with

45、in relative e of EX with probability 1-exp(e2 t FAIL(p)/4)lSo choose t to cancel other terms“High probability”t=O(log n/e2FAIL(p)Deviation by e with probability 1/n 101MITFor network reliabilitylRandom edge failuresEstimate FAIL(p)=Prgraph disconnectslNave Monte Carlo simulationChernoff bound-“tight

46、 concentration”Pr|X-EX|e EX 1/k1 satisfied clauses k1 sample value 1/klAdding O(k log n/e2)samples gives“large”meanlSo Chernoff says sample mean is probably good estimate109MITReliability ConnectionlReliability as DNF counting:Variable per edge,true if edge failsCut fails if all edges do(AND of edge

47、 vars)Graph fails if some cut does(OR of cuts)FAIL(p)=Prformula trueProblem:the DNF has 2n clauses110MITFocus on Small CutslFact:FAIL(p)pclTheorem:if pc=1/n(2+d)then Pra-mincut fails 1113MITAlgorithmlRCA can enumerate all a-minimum cuts with high probability in O(n2a)time.lGiven a-minimum cuts,can e

48、-estimate probability one fails via Monte Carlo simulation for DNF-counting(formula size O(n2a)lCorollary:when FAIL(p)n-(2+d),can e-approximate it in O(cn2+4/d)time114MITCombinelFor large FAIL(p),nave Monte CarlolFor small FAIL(p),RCA/DNF countinglBalance:e-approx.in O(mn3.5/e2)timelImplementations

49、show practical for hundreds of nodeslAgain,no way to verify correct115MITSummarylNave Monte Carlo simulation works well for common eventslNeed to adapt for rare eventslCut structure and DNF counting lets us do this for network reliability116MITConclusions117MITConclusionlRandomization is a crucial t

50、ool for algorithm designlOften yields algorithms that are faster or simpler than traditional counterpartslIn particular,gives significant improvements for core problems in graph algorithms118MITRandomized MethodslRandom selectionif most candidate choices“good”,then a random choice is probably goodlM

51、onte Carlo simulationsimulations estimate event likelihoodslRandom samplinggenerate a small random subproblemsolve,extrapolate to whole problemlRandomized Rounding for approximation119MITRandom SelectionlWhen most choices good,do one at randomlRecursive contraction algorithm for minimum cutsExtremel

52、y simple(also to implement)Fast in theory and in practice CGKLS120MITMonte CarlolTo estimate event likelihood,run trialslSlow for very rare eventslBias samples to reveal rare eventlFPRAS for network reliability121MITRandom SamplinglGenerate representative subproblemlUse it to estimate solution to wh

53、oleGives approximate solutionMay be quickly repaired to exact solutionlBias sample toward“important”or“sensitive”parts of problemlNew max-flow and min-cut algorithms122MITRandomized RoundinglConvert fractional to integral solutionslGet approximation algorithms for integer programsl“Sampling”from a w

54、ell designed sample space of feasible solutionslGood approximations for network design.123MITGeneralizationlOur techniques work because undirected graph are matroidslAll our results extend/are special casesPacking basesFinding minimum“quotients”Matroid optimization(MST)124MITDirected Graphs?lDirecte

55、d graphs are not matroidslDirected graphs can have lots of minimum cutslSampling doesnt appear to work125MITOpen problemslFlow in O(n2)time Eliminate v dependenceApply to weighted graphs with large flowsFlow in O(m)time?lLas Vegas algorithmsFinding good certificateslDetrministic algorithmsDeterministic construction of“samples”Deterministically compress a graph126MITRandomization in Graph Optimization ProblemsDavid KargerMIT127