approximation algorithm iterative rounding课件

《approximation algorithm iterative rounding课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ApproximationAlgorithm:IterativeRoundingLecture15:March9LowerboundandApproximationAlgorithmThekeyofdesigningapolytimeapproximationalgorithmistoobtainagood(lowerorupper)boundontheoptimalsolution.ForNP-completeproblem,wecan’tcomputeanoptimalsolutioninpolytime.

2、Thegeneralstrategy(foraminimizationproblem)is:lowerboundOPTSOLSOL≤c·lowerboundSOL≤c·OPTlowerboundOPTSOLTodesigngoodapproximationalgorithm,weneedagoodlowerbound.Forexample,if100·lowerbound≤OPTforsomeinstance,thenifwecompareSOLtolowerboundtoanalyzetheperforman

3、ce,wecouldnotachieveanythingbetterthanan100-approximationalgorithm.LowerboundandApproximationAlgorithmlowerboundOPTSOLGoal:tofindalowerboundasclosetoOPTaspossible.LowerboundandApproximationAlgorithmInmetricTSPandtheminimumSteinertreeproblem,weuseminimumspanni

4、ngtreeasalowerbound.Ingeneral,itisoftendifficulttocomeupwithagoodlowerbound.LinearProgrammingandApproximationAlgorithmlowerboundOPTSOLLinearprogramming:ageneralmethodtocomputealowerboundinpolytime.LPTocomputeranapproximatesolution,weneedtoreturnan(integral)so

5、lutionclosetoanoptimalLP(fractional)solution.AnExample:VertexCoverVertexcover:findanminimumsubsetofverticeswhichcoveralltheedges.Alinearprogrammingrelaxationofthevertexcoverproblem.Clearly,LPisalowerboundontheoptimalvertexcover,becauseeveryvertexcovercorrespo

6、ndstoafeasiblesolutionofthisLP.AnExample:VertexCoverHowbadisthisLP?111100.50.50.50.50.5LP=2.5OPT=4LP=n/2OPT=n-1AnExample:VertexCoverIntegralitygap:=Optimalintegersolution.Optimalfractionalsolution.Overallinstances.Invertexcover,thereareinstanceswherethisgapis

7、almost2.Half-integralityTheorem:Forthevertexcoverproblem,everyvertex(orbasic)solutionoftheLPishalf-integral,i.e.x(v)={0,½,1}Thereisa2-approximationalgorithmforthevertexcoverproblem.TheintegralitygapofthevertexcoverLPisatmost2.SurvivableNetworkDesignInputAnund

8、irectedgraphG=(V,E),Acostc(e)oneachedge,Aconnectivityrequirementr(u,v)foreachpairu,v.OutputAminimumcostsubgraphHofGwhichhasr(u,v)edge-disjointpathsbetweeneachpairu,v.(Thatis,Hsatisfiesall