the full steiner tree problem

《the full steiner tree problem》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ThefullSteinertreeproblemTheoreticalComputerScience306(2003)55-67C.L.Lu,C.Y.Tang,R.C.T.LeeReporter:Cheng-ChungLi2004/06/28OutlineDefinitionofSteinertreeApproximationAlgorithmsDefineoffullSteinertreeAgreedyapproximationalgorithmsratio3/2,insomespecialconditionratio8/5,inth

2、eworstcaseConclusionDefinitionofSteinertreeApproximationAlgorithmsDefinitionoffullSteinertreeAgreedyapproximationalgorithmsratio3/2,insomespecialconditionratio8/5,intheworstcaseConclusionDefinitionofSteinertree-(1)GivenagraphG=(V,E),asubsetRVofvertices,andalengthfunctiond

3、:E+ontheedges,asteinertreeisaconnectedandacyclicsubgraphofGwhichspansallverticesofRDefinitionofSteinertree-(2)TheverticesinRareusuallyreferredasterminalsandverticesinVRassteiner(oroptional)verticesNotethatasteinertreemightcontainthesteinervertices.Thelengthofasteinertreeisde

4、finedtobethesumofthelengthsofallitsedgesTheso-calledsteinertreeproblemistofindasteinerminimumtree,i.e.,steinertreeofminimumlengthPleaseseeFig155262234132234Fig1Applications&HardnessApplications:VLSIdesign,networkrouting,wirelesscommunications,computationalbiologyTheproblemiswel

5、lknowntobeNP-complete[R.M.Karp,1972],eveninEuclideanmetricorrectilinearmetricDefinitionofSteinertreeApproximationAlgorithmsDefinitionoffullSteinertreeAgreedyapproximationalgorithmsratio3/2,insomespecialconditionratio8/5,intheworstcaseConclusionApproximationAlgorithmsManyim

6、portantproblemsareNP-completeorworseTheyareapproximationalgorithmsHowgoodaretheapproximations?Wearelookingfortheoreticallyguaranteedbounds,notempiricalboundsSomeDefinitionsGivenanoptimizationproblem,eachprobleminstancexhasasetoffeasiblesolutionsF(x)EachfeasiblesolutionsF(x)has

7、acostc(s)Z+Theoptimumcostisopt(x)=minsF(x)c(s)foraminimizationproblemItsopt(x)=maxsF(x)c(s)foramaximizationproblemApproximationAlgorithmsLetalgorithmMonxreturnsafeasiblesolutionMisan-approximationalgorithm,where0,ifforallx,Foraminimizationproblem,Foramaximizationproblem,L

8、owerandUpperBoundsForaminimizationproblem:Soapproximat