Approximation Algorithms for k-Hurdle Problems

《Approximation Algorithms for k-Hurdle Problems》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ApproximationAlgorithmsfork-HurdleProblemsBrianC.Dean∗AdamGriffis∗OjasParekh†AdamWhitley∗December14,2009AbstractThepolynomial-timesolvablek-hurdleproblemisanaturalgeneralizationoftheclassicals-tminimumcutproblemwherewemustselectaminimum-costsubsetSoftheedgesofagraphs

2、uchthat

3、p∩S

4、≥kforeverys-tpathp.Inthispaper,wedescribeasetofapproximationalgorithmsfor“k-hurdle”variantsoftheNP-hardmultiwaycutandmulticutproblems.Forthek-hurdlemultiwaycutproblemwithrterminals,wegivetworesults,thefirstbeingapseudo-approximationalgorithmthatoutputsa(

5、k−1)-hurdlesolutionwhosecostisatmostthatofanoptimalsolutionforkhurdles.Secondly,weprovidea12(1−)-approximationalgorithmbasedonroundingthesolutionofalinearprogram,forwhichwegivearsimplerandomizedhalf-integralityproofthatworksforbothedgeandvertexk-hurdlemultiwaycutst

6、hatgeneralizesthehalf-integralityresultsofGargetal.forthevertexmultiwaycutproblem.Wealsodescribeanapproximation-preservingreductionfromvertexcoverasevidencethatitmaybedifficulttoachieve1abetterapproximationratiothan2(1−).Forthek-hurdlemulticutprobleminann-vertexgraph

7、,werprovideanalgorithmthat,foranyconstantε>0,outputsad(1−ε)ke-hurdlesolutionofcostatmostO(logn)timesthatofanoptimalk-hurdlesolution,andweobtaina2-approximationalgorithmfortrees.Keywords:multiwaycut,multicut,approximationalgorithm,randomizedrounding1IntroductionEver

8、sincetheearlyworkofFordandFulkerson[10],theminimums-tcutproblemanditsdual,themaximums-tflowproblem,havetogetherservedasacornerstoneforthefoundationofthefieldofcombinatorialoptimization.Numeroustheoreticalandpracticalapplicationsarebasedonthedualitybetweenminimums-tcu

9、tsandmaximums-tflows.Inthispaper,westudyanaturalgeneralizationoftheminimums-tcutproblemknownasthek-hurdleproblem,whoseobjectiveistochooseaminimum-costsubsetoftheedgesofagraphthatcutseverys-tpathatleastktimes.LettingG=(V,E)beagraphwithn=

10、V

11、verticesandm=

12、E

13、edgeswithco

14、stsc:E→R+,wecanwritethek-hurdleproblemasthefollowingintegerprogram,POPT=Minimizex(e)c(e)eP∈ESubjecttox(e)≥k∀p∈Pste∈px(e)∈{0,1}∀e∈E,wherePstdenote