【持续性肾脏替代治疗crrt英文精品课件】augmenting paths, witnesses and improved approximations for bounded degree msts

AugmentingPaths WitnessesandImprovedApproximationsforBoundedDegreeMSTs K Chaudhuri S Rao S Riesenfeld K TalwarUCBerkeley BDMST TheProblem Given Graph GEdgecosts ceDegreebound DFindaminimumcosttreethatrespectsthedegreebounds 2 1 2 1 2 2 1 1 1 1 2 2 BDMST D 3 MST BDMST TheProblem GeneralizationofMinimumCostHamiltonianPathForgeneralweightedgraphs NoPolynomial FactorApproximationunlessP NPOurWork Relaxdegreeboundstoobtainanapproximationincost PreviousResults FR94 UnweightedgraphsAdditive1approximationtodegree KR00 Weightedgraphs uniformdegreeboundsdeg v b 1 D logbncost T 1 1 OPT KR03 Non uniformdegreebounds CRRT QuasipolynomialRunningTimedeg v D logn loglogncost T OPT CRRT PolynomialRunningTimedeg v bD logbncost T OPT LPFormulation Primal min ecexe e2 v xe Dx2SPGDual max v minT C T v v degT v D MSTincostfunctioncuv u v v Penaltiesonhigh degreevertices AnAlgorithm SolveDualLPOptimalPenalties vPickMSTincostfunction cuv u v with LowmaximumdegreeLowactualcost AnAlgorithm SolveDualLPOptimalPenalties vPickMSTincostfunction cuv u v with Maximumdegree DRealcost OPT AnAlgorithm SolveDualLPOptimalPenalties vPickMSTincostfunction cuv u v with Maximumdegree D O logn loglogn Realcost OPT PickingtheRightTree TisMSTincostfunctioncuv u vwith Maxdegree D O logn loglogn Foreveryvertexvwith v 0 Mindegree D O logn loglogn Theorem ThasMaxdegree D O logn loglogn Actualcost OPT MSTDBProblem Given Graph GEdgecosts ceDegreeupperbound DHAsetofnodes LDegreelowerboundonL DLFindaMSTwithMaxdegree DHMindegreeofL DLOrprovethatnosuchtreeexists 1 1 2 1 2 1 1 1 1 1 2 1 DH 3 DL 2 L O PreviousWork FR94 Unweightedgraphs degreeupperboundsAdditive1approximation F93 DegreeupperboundsFindsanMSTwithmaxdegreebD logbnOrprovesnoMSTwithmaxdegreeDexists OurGuarantees Given Graph GEdgecosts ceDegreeupperbound DHAsetofnodes LDegreelowerboundonL DLWecanfindanMSTwith MaxDegree DH O logn loglogn MinDegreeofL DL O logn loglogn OrprovethatnoMSTwithgivenboundsexist FinalBDMSTAlgorithm SolveDualLPOptimalPenalties vRunourMSTDBalgorithm Costfunction cuv u vDegreeupperbound DL Setofnodeswith v 0Degreelowerbound DTheorem Failurecontradictsoptimalityof v MSTDBAlgorithmOutline StartwitharbitraryMSTT0Phasei Ti 1 useAugmentingPathstoReducethedegreeofa highdegree nodeOrincreasethedegreeofa lowdegree nodeSuccess NewtreeTiFailure WitnessforeitherDH dmax Ti 1 O logn loglogn orDL dmin L O logn loglogn UsefulEdgesandWitness Usefuledge OccursinsomeMSTofG e f Witness Structuretoshowalower upper boundonthedegreeofanyMST HighDegreeWitness HighdegreeWitness CenterSet WClusters C1 CkNousefulinterclusteredge InanyMST MaxDegree W d W k 1 W e W FeasibleSwaps Feasibleswap e f T TreeedgeeNon treeedgefUniquecycleinT fcontainsec e c f Afeasibleswap e f T ProducesanequalcosttreeReducesdegreeofendpointsofe 1 1 1 1 2 A D C B e f AugmentingPaths Algorithm Constructanaugmentingpathoffeasibleswaps W Ci 1 1 1 1 2 2 W Ci 1 1 1 1 2 2 W Ci 1 1 1 1 2 2 W Ci 1 1 1 1 2 2 AlgorithmOutline Startwith CenterSet W0Clusters connectedthroughW0Instepi FindanaugmentingpathoffeasibleswapstoimprovesomevinWiFailure CenterSetandclustersformahighdegreewitness Conclusion Improvedapproximationfor BDMST BoundedDegreeMST MSTDB MSTwithDegreeBounds NewTechniques ImprovedcostboundingtechniquesbasedonEdmond smatchingalgorithmImproveddegreeimprovementtechniquesbasedonaugmentingpathsOpenQuestion Candegreeboundsberelaxedtoadditiveconstant FR94 Givesadditive1forunweightedgraphs Questions Reduce Max Degree Initialize LetSd nodeswithdegreedormorePickd Sd 1 logn loglogn Sd CenterSet W0 Sd Sd 1Initialclusters ComponentswhenW0isdeletedfromT W Ci 2 2 Reduce Max Degree Foreachusefulinterclusteredgef Findfeasibleswap e f T thatimprovesv2WtRemovevfromWtFormnewclusterwith efvchildrenclustersofv 2 2 1 1 2 2 2 2 2 2 Reduce Max Degree TerminationConditions DegreedvertexvremovedfromWt CanfindasequenceofswapstoimprovevNumberofdegreedverticesdecreasesbyone 2 2 2 2 1 1 2 2 1 1 2 2 1 1 2 2 Reduce Max Degree TerminationConditions DegreedvertexvremovedfromWt CanfindasetofswapswhichimprovevNumberofdegreedverticesdecreasesbyoneNofeasibleinterclusteredges CanfindwitnesstoshowthatmaxdegreeofanyMSTisatleastd O logn loglogn ObtainingaWitness CenterSet Wt Wt Sd Clusters FromdeletingWt d 2 Wt Lostfrommerges Sd 1 Total d 2 Wt Sd 1 WitnessQuality Atleast d 2 O logn loglogn Summary Improvedapproximationfor BDMST BoundedDegreeMST MSTDB MSTwithDegreeBounds NewTechniques ImprovedcostboundingtechniquesbasedonEdmond smatchingalgorithmImproveddegreeimprovementtechniquesbasedonaugmentingpathsOpenQuestion Candegreeboundsberelaxedtoadditiveconstant FR94 Givesadditive1forunweightedgraphs ABetterAlgorithm SupposegivenDH wecanfindanMSTwith MaxDegree 5DH 2OrshowthereisnoMSTwithmaxdegreeDHBDMSTGuarantees deg v 10 1 D O 1 cost T 1 1 OPTMSTDBAlgorithmusesPush Relabel PushRelabel G85 GT86 Anodehas ALabelAnExcessPush PushflowfromahighertoalowerlabelalonganedgeRelabel RaisethelabelofanodewithnoedgestoalowerlabelFeasibility NodeatlabelLhasedgestonodesatlabelL 1orabove PushRelabelforMaxFlow Initially Source 1excessSink 1deficitAllothernodes 0excessPushandRelabeluntil NonodehasanyexcessOrthereisalabelwithnonodes A Push RelabelforMSTDB WorksforMSTDBwithdegreeupperboundsonlyEachnodehas AlabelAnexcess deficitdegreeExcessandDeficits deg v d deg v d 1 unitsexcessdeg v d 1 d 1 deg v unitsdeficit Push RelabelforMSTDB Push AnodecantransferdegreetoanodeatalowerlabelRelabel RaisethelabelofanodewhichcannottransferdegreetoanynodeatalowerlevelFeasibility AnodeatlabelLcanbeimprovedonlybynodesatlabelL 1orhigher AlgorithmOutline SparseLabel Haslessthan4timesasmanynodesasthenumberofnodesinallthelabelsaboveitAlgorithm Pushandrelabeluntil EithernonodeshaveanyexcessOrthereisasparselabelSparseLabel WitnessAveragedegree d 5 2 Publications Manuscripts CRRT ImprovedApproximationAlgorithmsforDegreeBoundedMSTsusingPush Relabel CRRT WhatwouldEdmondsdo AugmentingPathsandWitnessesforDegreeBoundedMSTs CCWBPK04 SelfishCachinginDistributedSystems AGameTheoreticApproach PODC2004 CGRT03 Paths TreesandMinimumLatencyTours FOCS2003 FutureDirections BoundedDegreeMSTs Improveguaranteesto deg v B O 1 cost T OPTEmbeddingsimplemetricstol1withlowdistortion Questions PickingtheRightTree Proof Wecanshowthat C TD v D v degTD v D OPTDIfdegTD v Dwhen D v 0C TD OPTD PickingtheRightTree KR00 OurWork F93 MaxDegree bB logbn MaxDegreeB O logn loglogn Technicalslidewithequationabouthowimposingbothupperandlowerboundsondegreesgivesusoptimalcost PickingtheRightTree KR00 OurWork Guarantees For 0Maxdegree 1 bB logbnMaxCost 1 1 OPTRunningtime Polynomial Guarantees Maxdegree B O logn loglogn MaxCost OPTRunningTime Quasipolynomial Augmentingpathsandwitne