A note on optimal communication spanning trees

BangYeWu

Kun–MaoChao

April1,2004

Theoptimalcommunicationspanningtree(OCT)problemisdefinedasfollows.LetG=(V,E,w)beanundirectedgraphwithnonnegativeedgelengthfunctionw.Wearealsogiventherequirementsλ(u,v)foreachpairofvertices.ForanyspanningtreeTofG,thecommunicationcostbetweentwoverticesisdefinedtobetherequirementmultipliedbythepathlengthofthetwoverticesonT,andthecommunicationcostofTisthetotalcommunicationcostsummedoverallpairsofvertices.Ourgoalistoconstructaspanningtreewithminimumcommunicationcost.

󰀁

Thatis,wewanttofindaspanningtreeTsuchthatu,v∈Vλ(u,v)dT(u,v)isminimized.

TherequirementsintheOCTproblemarearbitrarynonnegativevalues.Byrestrictingtherequirements,severalspecialcasesoftheproblemweredefinedintheliterature.Welistthe

+

problemsinthefollowing,inwhichr:V→Z0isagivenvertexweightfunctionandS⊂Visasetofkverticesgivenassources.

•λ(u,v)=1foreachu,v∈V:ThisversionistheMinimumRoutingCostSpanningTree(MRCT)problemdiscussedinthepreviouschapter.•λ(u,v)=r(u)r(v)foreachu,v∈V:ThisversioniscalledtheOptimalProduct-RequirementCommunicationSpanningTree(PROCT)problem.

•λ(u,v)=r(u)+r(v)foreachu,v∈V:ThisversioniscalledtheOptimalSum-RequirementCommunicationSpanningTree(SROCT)problem./S:Thisversioniscalledthep-SourceOCT(p-OCT)problem.Inother•λ(u,v)=0ifu∈

󰀁󰀁

words,thegoalistofindaspanningtreeminimizingu∈Sv∈Vλ(u,v)dT(u,v).

•λ(u,v)=1ifu∈S,andλ(u,v)=0otherwise:Thisversioniscalledthep-SourceMRCT(p-MRCT)problem.Inotherwords,thegoalistofindaspanningtreeminimiz-󰀁󰀁

ingu∈Sv∈VdT(u,v).WedefinetwocommunicationcostsandnotationsforthePROCTandtheSROCTproblems.Definition1:Theproduct-requirementcommunication(orp.r.c.inabbreviation)costofatree

󰀁

TisdefinedbyCp(T)=u,vr(u)r(v)dT(u,v).

Whentherearemorethanonevertexweightfunctions,weshalluseCp(T,r)toindicatethatthecostiswithrespecttoweightr.

Definition2:Thesum-requirementcommunication(ors.r.c.inabbreviation)costofatreeTis

󰀁

definedbyCs(T)=u,v(r(u)+r(v))dT(u,v).

GivenagraphG,thePROCT(orSROCT)problemasksforaspanningtreeTofGsuchthatCp(T)(orCs(T)respectively)isminimumamongallpossiblespanningtrees.

1

r󰀀(󰀀b󰀀)=0󰀀

3󰀀r󰀀(󰀀c󰀀)=1󰀀

2󰀀r󰀀(󰀀d󰀀)=2󰀀

2󰀀1󰀀r󰀀(󰀀a󰀀)=3󰀀r󰀀(󰀀e󰀀)=1󰀀Figure1:Theproduct-requirementcommunicationcostbetweenverticesaanddis3×2×(2+

3+2)=42,andthesum-requirementcommunicationcostbetweenverticesaandeis(3+1)×(2+3+1)=24.

Optimal󰀀 Communication Spanning Trees󰀀more general󰀀PROCT󰀀SROCT󰀀p-source OCT, fixed p󰀀2-source OCT󰀀p-source MRCT, arbitrary p󰀀MRCT󰀀p-source MRCT, fixed p󰀀2-source MRCT󰀀Figure2:TherelationshipoftheOCTproblems.

Example1:Thep.r.c.costands.r.c.costbetweenapairofverticesareillustratedinFigure1.

Thecostofthetreeisthesumofthecostforallpairsofvertices.

TherelationshipofthedifferentversionsoftheOCTproblemsisillustratedinFigure2.Notethattherearevariantsforthemulti-sourceproblems.By“arbitraryp,”wemeanthereisnorestrictiononthenumberofsourcesintheinputdata,whileby“fixedp,”thenumberofsourcesisalwaysequaltotheconstantp.

Table1summarizestheresults.

BibliographicNotesandFurtherReading

ThecurrentbestapproximationratioforthegeneralOCTproblemisduetoYairBartal’salgorithmswhichapproximatearbitrarymetricsbytreemetrics.Hefirstpresentedarandomizedalgorithm[1]andthenderandomizedittoadeterministicalgorithm[2].ItsapplicationtoapproximatingtheOCTproblemwaspointedoutin[10].

ThePROCTandSROCTproblemswereintroducedin[8].Inthatpaper,BangYeWu,Kun-MaoChao,andChuanYiTanggavea1.577-approximationalgorithmforthePROCTproblemanda2-approximationalgorithmfortheSROCTproblem.ThePTASusingtheScaling-and-RoundingtechniqueforaPROCTproblemwaspresentedin[9]bythesameauthors.Scalingtheinputinstancesisatechniquethathasbeenusedtobalancetherunningtimeandtheapproximationratio.Forexample,OscarH.IbarraandChulE.Kimusedthescalingtechniquetodevelopa

2

Table1:TheobjectivesandcurrentlybestratiosoftheOCTproblems.

ProblemOCTPROCTSROCTMRCTp-MRCT2-MRCT

Objective

󰀁u,v

Ratio

O(lognloglogn)PTAS2PTAS2PTAS

λ(u,v)dT(u,v)r(u)r(v)dT(u,v)

+r(v))dT(u,v)

󰀁u,v

󰀁󰀁u,v(r(u)u,v

dT(u,v)

󰀁v∈V

󰀁u∈S

dT(u,v)

󰀁v

(dT(s1,v)+dT(s2,v))

fullypolynomialtimeapproximationscheme(FPTAS)fortheknapsackproblem[5],andsomeimprovementwasmadebyEugeneL.Lawler[6].Aniceexplanationofthetechniquecanalsobefoundin[4](pp.134–137).

TheNP-hardnessofthe2-MRCTwasshownbyBangYeWu[7],inwhichthereductionisfromtheExactCoverBy3-Sets(X3C)problem([SP2]in[4]).Thetransformationissimplerandeasiertoextendtotheweightedcase,whichisdesignedtoshowtheNP-hardnessofthep-MRCTproblemforanyfixedp.Asimilarreduction(for2-MRCT)wasalsoshownbyHaroldConnamacherandAndrzejProskurowski[3].Theyshowedthatthe2-MRCTproblemisNP-hard.ThePTASforthe2-MRCTproblemalsoappearedin[7].InadditiontothePTASforthe2-MRCTproblem,thereisalsoaPTASfortheweighted2-MRCTproblem.ButthePTASworksonlyformetricinputsandthecounterpartongeneralgraphswasleftasanopenproblem.

References

[1]Y.Bartal.Probabilisticapproximationofmetricspacesanditsalgorithmicapplications.In

Proceedingsofthe37thAnnualIEEESymposiumonFoundationsofComputerScience,pages184–193,1996.[2]Y.Bartal.Onapproximatingarbitrarymetricsbytreemetrics.InProceedingsofthe30th

AnnualACMSymposiumonTheoryofComputing,pages161–168,1998.[3]H.S.ConnamacherandA.Proskurowski.Thecomplexityofminimizingcertaincostmetrics

fork-sourcespanningtrees.DiscreteAppl.Math.,131:113–127,2003.[4]M.R.GareyandD.S.Johnson.ComputersandIntractability:AGuidetotheTheoryofNP-Completeness.W.H.FreemanandCompany,SanFrancisco,1979.[5]O.H.IbarraandC.E.Kim.Fastapproximationalgorithmsfortheknapsackandsumofsubset

problems.J.ACM,22:463–468,1975.[6]E.L.Lawler.Fastapproximationalgorithmsforknapsackproblems.

4(4):339–356,1979.

Math.Oper.Res.,

3

[7]B.Y.Wu.Apolynomialtimeapproximationschemeforthetwo-sourceminimumroutingcost

spanningtrees.J.Algorithms,44:359–378,2002.[8]B.Y.Wu,K.-M.Chao,andC.Y.Tang.Approximationalgorithmsforsomeoptimumcommu-nicationspanningtreeproblems.DiscreteAppl.Math.,102:245–266,2000.[9]B.Y.Wu,K.-M.Chao,andC.Y.Tang.Apolynomialtimeapproximationschemeforoptimal

product-requirementcommunicationspanningtrees.J.Algorithms,36:182–204,2000.[10]B.Y.Wu,G.Lancia,V.Bafna,K.-M.Chao,R.Ravi,andC.Y.Tang.Apolynomialtime

approximationschemeforminimumroutingcostspanningtrees.SIAMJ.Comput.,29:761–778,2000.

4