资源描述：
《ApproximationAlgorithmsforMin-k-overlap.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、ApproximationAlgorithmsforMin-k-overlapProblemsUsingthePrincipalLatticeofPartitionsApproachHNarayananI,SubirRoy2,andSachinPatkara1Deptt.ofElec.Engg.,IIT,Bombay400076,INDIA2Deptt.ofElec.Engg.,IITKanpur,208016,INDIA3ForschungsinstitutffirDiskreteMathematik,UniversitsBonn,Germany1Introdu
2、ctionInthispaperwediscussstrategiesforconstructingapproximatealgorithmsforsolvir/gtheMin-k-cutproblem,theMin-k-vertexsharingproblemandtheirgeneralizationtheMin-k-overlapproblem.Ineachcase,wefirstformulateanappropriatesubmodularfunctionandconstructitsPrincipalLatticeofPartitions(PLP)[1
3、1].ApplyinganelementarystrategyonanappropriatesubintervalofthePLPyieldstheapproximatealgorithms.WestatetheMin-k-cutMin-k-ver~exsharing,andtheMin-k-overlapprob-lems.LetGbeagraphwithnonnegativeweightsontheedges.Min-k-cutProblem:PartitionthevertexsetV(G)ofGintoksubsetssuchthatthesumofthe
4、weightsofedgeswhoseendpointslieindifferentblocksisaminimum.Min-k-vertexsharingProblem:PartitiontheedgesetE(G)ofGintoksubsetssuchthatthesumoftheweightsofverticessharedbetweensubsetsisminimised.Thisproblemhastwovariations.Vertexsharing(1):Counteachvertexsharedbetweentblocks(t-1)times.Ve
5、rtexsharing(2):Hereasharedvertexiscountedonlyonce.Min-k-overlapProblem:Letpbeapolymatroidrankfunctiononthesub-setsofS(i.e.p(X)+#(Y)>_#(XOY)+#(XNY),VX,YCS,#isincreasingandp(O)=0).Findthekblockpartition{N~,...,Nk}ofEsuchthat~/k=lp(Ni)-tL(S)isaminimum.TheMin-k-cutproblemisaspecialcaseoft
6、heMin-k-overlapproblemifwetakeStobeV(G)and#(X)tobethesumoftheweightsofedgesincidentontheverticesinX.TheMin-k-vertexsharing(1)isobtainedifwetakeStobeE(G)and#(X)tobethesumoftheweightsofverticesincidentonedgesinX.Vertexsharing(2)isobtainedifwetake#(X)=~eexw(F(e))-w(E(X))wherew(F(e))isthe
7、sumofweightsofverticesincidentoneandw(E(X))isthesumofweightsofverticeswhichareincidentonedgesinXbutnotonedgesin(E(G)-X).ForconvenienceandgreatergeneralitywepresentourresultsintermsofBi-partitegraphs(whichmayberegardedasrepresentinghypergraphs).TheabovementionedproblemsareNP-Hard(see,f
8、orexa
