资源描述：
《Primal-Dual Method》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、ORIE634ApproximationAlgorithmApril21,2012Lecture8Lecturer:Yang.LiScribe:Yang.Li8.1ThePrimal-DualMethod8.1.1TheBasicMethodOurmeta-methodfordesigningapproximationalgorithms:1.Formulateproblemasanintegerprogram2.RelaxtoanLP3.UseLPtoobtainanewoptimalsolutionAnexampl
2、e:HittingSet�Input:—groundsetE={e1,e2,...,en}—subsetsT1,T2,...,Tp⊆E—costsce≥0e∈E�Goal:Findmin-costA⊆Es.t.A∩Ti≠ϕ∀i.1OurBasicMethod:Step1Min∑cexee∈Es.t.∑xe≥1∀ie∈Tixe∈{0,1}Step2RelaxittoanLP:xe∈{0,1}→xe≥0Step3Considerthedualprogramming:Max∑yiis.t.∑ye≤ce∀ei:e∈Tiyi≥0
3、BasicIdeaofPrimal-DualMethod:Startfromandualfeasiblesolution(notnecessaryoptimal)i.e.y←0;whiletheredoesnotexistanintegralsolutionobeyingprimalcomplementaryslacknessxe≥0⇒∑ye=cei:e∈Tiwethengetadirectionofincreasefordual;continuethisprocessandatlastwewillgetaprimal
4、feasiblesolutionobeyingprimalcomplementaryslackness.2Algorithm1:Primal-Dual1y←0A←ϕWhileAisnotfeasibleFindviolatedTk(i.e.Tks.t.A∩Tk=ϕ)Increaseykuntil∃e∈Tks.t.∑ye=cei:e∈TiA←A∪{e}ReturnAPerformanceGuaranteeAnalysis:BytheconstructionofA,∑ce=∑∑yi=∑A∩Tiyie∈Ae∈Ai:e∈Tii
5、Ifthereexistsanαs.t.A∩Ti≤α,thenwehave:∑ce≤α∑yi≤αOPT,e∈Aiandtheabovealgorithmwouldbeanα-approximationalgorithm.ASpecialCase:VertexCoverProblemisaspecialcaseofHittingSetProblem,because:—groundsetV—subsetsTi={u,v}foreach(u,v)∈E—costsce≥0e∈VObviously,Ti=2⇒A∩Ti≤2⇒a2-
6、approximationalgorithm.3Application1:FeedbackVertexSetProblemFeedbackVertexSetinUndirectedGraphs�Input:—undirectedgraphG=(V,E)—weightswi≥0∀i∈V�Goal:FindS⊆Vminimizing∑wis.t.for∀cycleCinG,C∩S≠ϕ.i∈S(Equivalently,findamin-weightsetofverticesSs.t.removingSfromthegrap
7、hcausestheremaininggraphtobeacyclic.)FormulatedasaHittingSetProblem:�GroundsetV�Costswi�Setstohit:Ti=CiforeachcycleCiingraphAnimportantFactconcerningthisproblem:IntheFeedbackVertexSetProblem,everyinputgraphG⇔agraphG'withnodegree1verticesandeverydegree2vertexisad
8、jacenttoavertexofhigherdegree.TheoreticalPreparation:Lemma8.1Ineverynon-emptygraphinwhichtherearenodegree1verticesands.t.Foreachvertexofdegree2everyneighborhashigherd
