资源描述：
《Approximation Algorithms for Minimum K-cut 7》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、ApproximationalgorithmsforminimumK-cut1NiliGuttmann-BeckandRefaelHassinAbstractLetG=(V;E)beacompleteundirectedgraph,withnodesetV=fv;:::;vgand1nedgesetE.Theedges(v;v)2Ehavenon-negativeweightsthatsatisfythetriangleijPppinequality.GivenasetofintegersK=fkg(kjVj),theminimumK-cutiii=1i=1p
2、problemistocomputedisjointsubsetswithsizesfkg,minimizingthetotalweightii=1ofedgeswhosetwoendsareindi erentsubsets.Wedemonstratethatforany xedpitispossibletoobtaininpolynomialtimeanapproximationofatmost3timestheoptimalvalue.Wealsoproveboundsontheratiobetweentheweightsofmaximumandminim
3、umcuts.1IntroductionLetG=(V;E)beacompleteundirectedgraphwithnon-negativeedgeweightsl(e)e2E,PppandletKbeasetofppositiveintegersfkgsuchthatkjVj.AK-cutisacollec-iii=1i=1ptionofdisjointsetsfPgsuchthat8i2f1;:::;pgjPj=k.TheminimumK-cutproblemiiii=1PPPPp?1pisto ndaK-cutsuchthatl(P;P)(where
4、l(P;P)=l(v;u))isijijv2Pu2Pi=1j=i+1ijminimized.PpTheversionofthisprobleminwhichk=jVjandthesizesofthesetsarenotgivenii=1buttheirnumberisrequiredtobep,andpis xed,ispolynomiallysolvable[2].Whenp2ispartoftheinput,thisversionisNP-hard[1]andSaranandVazirani[3]gavea2?papproximationalgorithm.
5、If,inaddition,thesetsinthepartitionarerestrictedtobeofequalsize,theproblemisonlyknowntobeapproximablewithinjVj(p?1)=pbySaranandVazirani[3].WeconsidertheminimumK-cutproblemundertheassumptionthattheweightssatisfythetriangleinequality.TheproblemisstillNP-hardunderthisassumptionbecauseea
6、chgraphcanbemadetosatisfythetriangleinequalitywhilenotchangingtheproblembyPaddingahighenoughconstant(forexample,l(e))toalltheedgelengths.e2EWedemonstratethatforany xedpitispossibletoobtaininpolynomialtimeanapproximationofatmost3timestheoptimalvalue.1DepartmentofStatisticsandOperation
7、sResearch,TelAvivUniversity,TelAviv69978,Israel.fnili,hassing@math.tau.ac.il1PpSupposenowk=jVj(partitioningallthenodesinthegraph).Letl;lbeimaxmini=1lmaxtheweightsofthemaximumandminimumcutsinthegraph,respectively,andletr=.lminWeproveboundsonrforseveralinterestingcases,assumingthetrian
8、gleinequalit
