RAJAJOTHI
NationalInstitutesofHealth
AND
BALAJIRAGHAVACHARI
UniversityofTexasatDallas
Abstract.GivenanundirectedgraphG=(V,E)withnonnegativecostsonitsedges,arootnoder∈V,asetofdemandsD⊆Vwithdemandv∈Dwishingtoroutew(v)unitsofflow(weight)tor,andapositivenumberk,theCapacitatedMinimumSteinerTree(CMStT)problemasksforaminimumSteinertree,rootedatr,spanningtheverticesinD∪{r},inwhichthesumofthevertexweightsineverysubtreeconnectedtorisatmostk.WhenD=V,thisproblemisknownastheCapacitatedMinimumSpanningTree(CMST)problem.BothCMsTandCMSTproblemsareNP-hard.Inthisarticle,wepresentapproximationalgorithmsfortheseproblemsandseveraloftheirvariantsinnetworkdesign.Ourmainresultsarethefollowing:
—Wepresenta(γρST+2)-approximationalgorithmfortheCMStTproblem,whereγistheinverseSteinerratio,andρSTisthebestachievableapproximationratiofortheSteinertreeproblem.Ourratioimprovesthecurrentbestratioof2ρST+2forthisproblem.
—Inparticular,weobtain(γ+2)-approximationratiofortheCMSTproblem,whichisanimprovementoverthecurrentbestratioof4forthisproblem.ForpointsinEuclideanandrectilinearplanes,ourresulttranslatesintoratiosof3.1548and3.5,respectively.
—Forinstancesintheplane,undertheLpnorm,withtheverticesinDhavinguniformweights,wepresentanontrivial(7ρ+3)-approximationalgorithmfortheCMStTproblem.Thistranslates5ST2intoaratioof2.9fortheCMSTproblemwithuniformvertexweightsintheLpmetricplane.Our
ResearchsupportedinpartbytheNationalScienceFoundationundergrantCCR-9820902.AnextendedabstractofthisarticleappearedinJothiandRaghavachari[2004a].
Authors’addresses:R.Jothi,NationalCenterforBiotechnologyInformation,NationalLibraryofMedicine,NationalInstitutesofHealth,8600RockvillePike,Bethesda,MD20894,e-mail:jothi@ncbi.nlm.nih.gov;B.Raghavachari,DepartmentofComputerScience,UniversityofTexasatDallas,Richardson,TX75080,e-mail:rbk@utdallas.edu.
C2005AssociationforComputingMachinery.ACMacknowledgesthatthiscontributionwasau-thoredorco-authoredbyacontractororaffiliateofthe[U.S.]Government.Assuch,theGovernmentretainsanonexclusive,royalty-freerighttopublishorreproducethisarticle,ortoallowotherstodoso,forGovernmentpurposesonly.
Permissiontomakedigitalorhardcopiesofpartorallofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitordirectcommercialadvantageandthatcopiesshowthisnoticeonthefirstpageorinitialscreenofadisplayalongwiththefullcitation.CopyrightsforcomponentsofthisworkownedbyothersthanACMmustbehonored.Abstractingwithcreditispermitted.Tocopyotherwise,torepublish,topostonservers,toredistributetolists,ortouseanycomponentofthisworkinotherworksrequirespriorspecificpermissionand/orafee.PermissionsmayberequestedfromPublicationsDept.,ACM,Inc.,1515Broadway,NewYork,NY10036USA,fax:+1(212)869-0481,orpermissions@acm.org.C2005ACM1549-6325/05/1000-0265$5.00
ACMTransactionsonAlgoritms,Vol.1,No.2,October2005,pp.265–282.
266R.JOTHIANDB.RAGHAVACHARI
ratioof2.9solvesthelong-standingopenproblemofobtaininganyratiobetterthan3forthiscase.
—FortheCMSTproblem,weshowhowtoobtaina2-approximationforgraphsinmetricspaceswithunitvertexweightsandk=3,4.
—ForthebudgetedCMSTproblem,inwhichtheweightsofthesubtreesconnectedtorcouldbeup
2
toαkinsteadofk(α≥1),weobtainaratioofγ+α.CategoriesandSubjectDescriptors:F.2.2[AnalysisofAlgorithmsandProblemComplexity]:Non-numericalAlgorithmsandProblems;G.2.1[DiscreteMathematics]:Combinatorics;G.2.2[DiscreteMathematics]:GraphTheoryGeneralTerms:Algorithms,Theory
AdditionalKeyWordsandPhrases:Spanningtrees,minimumspanningtrees,approximationalgo-rithms,networkdesign
1.Introduction
Inthisarticle,weconsidertheCapacitatedMinimumSteinerTree(CMStT)prob-lem,oneoftheextensivelystudiednetworkdesignproblemsintelecommunica-tions[Ambergetal.1996;Voß2001].TheCMStTproblemcanformallybedefinedasfollows:
GivenanundirectedgraphG=(V,E)withnonnegativecosts
onitsedges,arootnoder∈V,asetofdemandsD⊆Vwithdemandv∈Dwishingtoroutew(v)unitsofflow(weight)tor,andapositivenumberk,theCapacitatedMinimumSteinerTree(CMStT)problemasksforaminimumSteinertree,rootedatr,spanningtheverticesinD∪{r},inwhichthesumofthevertexweightsineverysubtreeconnectedtorisatmostk.
FortheCMStTproblem,thecapacityconstraintkmustbeatleastasmuchasthelargestvertexweightinordertobeabletofindafeasiblesolution.Sincethecasewithk=∞istheminimumSteinertreeproblem,whichisNP-hard,theCMStTproblemisNP-hard.WhenD=V,theCMStTproblemisthewell-knownCapacitatedMinimumSpanningTree(CMST)problem.TheCMSTproblemisNP-hard[GareyandJohnson1979;Papadimitriou1978]evenforthecasewhenverticeshaveunitweightsandk=3.Theproblemispolynomial-timesolvableifallverticeshaveunitweightsandk=2[GareyandJohnson1979].Theproblemcanalsobesolvedinpolynomialtimeifverticeshave0,1weightsandk=1,butremainsNP-hardifverticeshave0,1weights,k=2,andalledgelengthsare0or1[GareyandJohnson1979].Eventhegeometricversionoftheproblem,inwhichtheedgecostsaredefinedtobetheEuclideandistancebetweentheverticestheyconnect,remainsNP-hard.
Intelecommunicationnetworkdesign,theCMSTproblemisthatofdesigningaminimum-costtreenetworkbyinstallingexpensive(suchasfiber-optic)cablesalongitsedges.Thecableshaveprespecifiedcapacitiesontheamountofdemandtheycanhandle,andcanbeboughtatacertaincostperunitlength.Everysourcenodeinthenetworkhassomedemandthatithastotransmittothesinknode.Theobjectiveistoconstructaminimum-costtreenetworkforsimultaneousroutingofdemandsfromthesourcenodestothesinknode.
AgeneralizationoftheCMStTproblemistheSingleSinkBuy-at-Bulk(SSBB)probleminwhichwearegiventheoptionofusingldifferentcabletypes,insteadof
CMStT:
CapacitatedMinimumSpanningTreeProblem267
justone[Salmanetal.1997].Eachcablehasadifferentcapacityconstraintandthecostofthecablesobeys“economyofscale.”Onemajordifferenceisthatthereisnorestrictionthatthefinalnetworkneedstobeatree.AnothervariationistheCapacitatedMinimumSpanningNetworkproblemwithconnectivitycon-straints[JothiandRaghavachari2004b].
TheCMSTproblemhasbeenwellstudiedincomputerscienceandoperationsresearchforthepast40years.Numerousheuristicsandexactalgorithmshavebeenproposed(seeSection1.3formoredetails).Althoughmostoftheheuristicssolveseveralwell-knowninstancesclosetooptimum,theydonotprovideanyapproximationguaranteeonthequalityofthesolutionsobtained.Exactproceduresarelimitedtosolvingsmallerinstancesbecauseoftheirexponentialrunningtime.Inthisarticle,wepresentimprovedapproximationalgorithmsfortheCMStTandCMSTproblemsandtheirvariants.
1.1.PREVIOUSRESULTS.FortheCMSTproblemwithuniformvertexweights,GavishandAltinkemer[1986]presentedamodifiedparallelsavingsalgorithm(PSA)withapproximationratio4−1/(2logk−1).AltinkemerandGavish[1988]
2
gaveimprovedapproximationalgorithmswithratios3−kand4fortheuniformandnonuniformvertexweightcases,respectively.Theyconstructedatravelingsales-mantour(TSP)withlengthofatmosttwicetheminimumspanningtree(MST),andpartitionedthetourintosegments(subtrees)ofweightatmostk.Partitionedsub-treeswerethenconnectedtotherootvertexusingdirectedges.Hassinetal.[2000]presentedalgorithmsforthe1-cableSSBBproblem.ThealgorithmsbyAltinkemerandGavish[1988]andHassinetal.[2000]canbeusedtoobtainratiosof2ρST+1and2ρST+2fortherespectiveuniformandnonuniformvertexweightCMStTproblems.1.2.OURCONTRIBUTIONS.Inthisarticle,wesolvethelong-standingopenproblemofobtainingbetterapproximationratiosfortheCMSTproblem.Ourmainresultsarethefollowing:
—Wepresenta(γρST+2)-approximationalgorithmfortheCMStTproblem,whereγistheinverseSteinerratio,1andρSTisthebestachievableapproximationratiofortheSteinertreeproblem.Ourratioimprovesthecurrentbestratioof2ρST+2forthisproblem.
—Inparticular,weobtain(γ+2)-approximationratiofortheCMSTproblem,whichisanimprovementoverthecurrentbestratioof4forthisproblem.ForpointsinEuclideanandrectilinearplanes,ourresulttranslatesintoratiosof3.1548and3.5,respectively.
—Forinstancesintheplane,undertheLpnorm,withtheverticesinDhavinguniformweights,wepresentanontrivial(7ρ+3)-approximationalgorithm5ST2fortheCMStTproblem.Thistranslatesintoaratioof2.9fortheCMSTproblemwithuniformvertexweightsintheLpmetricplane.Ourratioof2.9solvesthelong-standingopenproblemofobtainingaratioanybetterthan3forthiscase.—FortheCMSTproblem,weshowhowtoobtaina2-approximationforgraphsinmetricspaceswithunitvertexweightsandk=3,4.
1
TheSteinerratioisthemaximumratioofthecostsoftheminimumcostSteinertreeversustheminimum-cost√spanningtreeforthesameinstance.Ingraphsγ=2,andinEuclideanandrectilinearmetricsitis2/3and3/2,respectively.
268R.JOTHIANDB.RAGHAVACHARI
—ForthebudgetedCMSTproblem,inwhichtheweightsofthesubtreesconnected
2
torcouldbeuptoαkinsteadofk(α≥1),weobtainaratioofγ+α.Oftheaboveresults,the2.9-approximationresultfortheCMSTproblemisofmostsignificance.Thisisduetothefactthatobtainingaratioanybetterthan3forgraphsdefinedintheEuclideanplane(withuniformvertexweights)isnotstraightforward.Thereareseveralwaysonecanobtainaratioof3forthisproblem(AltinkemerandGavish[1988],avariationofthealgorithminHassinetal.[2000],ouralgorithminSection3.1).Butthequestionwaswhetheronecaneverobtainaratiosmallerthan3−o(1)forthisversionoftheCMSTproblem.Wepresentanexample(inSection5),whichshowsthat,withthecurrentlyavailablelowerboundsfortheCMSTproblem,itisnotpossibletoobtainanapproximationratioanybetterthan2.WeintroduceanovelconceptofX-treestoovercomethedifficultiesinobtainingaratiobetterthan3.
Achievingratiosbetterthan3and4fortheuniformandnonuniformvertexweightedCMSTproblems,respectively,hasbeenanopenproblemforover15yearsnow.Onemajorreasonforthedifficultyinfindingbetterapproximationsisthatthereisnonontriviallowerboundforanoptimalsolution.Thereareinstancesforwhichthecostofanoptimalsolutioncanbeasmuchas(n/k)timesthatofanMST.Theinabilitytofindbetterlowerboundshasgreatlyimpededtheprocessoffindingbetterapproximationratiosforthisproblem.EventhoughwewerenotabletocompletelyeliminatetheuseofMSTasalowerbound,wefoundwaystoexploititsgeometricstructure,therebyachievingbetterperformanceratios.UnlikethealgorithmsinAltinkemerandGavish[1988],inwhichtheMSTlowerboundcontributesafactorof2tothefinalratio,ouralgorithmsminimizetheuseoftheMSTlowerbound,therebyachievingbetterratios.
1.3.RELATEDWORK.AlgorithmsforfindinganMSTwithnoconstraintsarewellknown.Infact,thosealgorithmscanbemodifiedtofindafeasibleCMST,albeitwithnoguaranteedapproximationratio.ThecelebratedclusteringtechniqueofGoemansandWilliamson[1995]canbeusedtoapproximatetheCMSTproblembypartitioningthegivensetofnnodesintogroupsofweightexactlyk,formaMSTforeachgroup,andconnecteachtreetotherootnode.Theapproximationratioof
12
suchanapproachwouldbe4(1−k)+1.
Thereareseveralexactalgorithmsandmathematicalformulations[ChandyandLo1973;ChandyandRussell1972;EliasandFerguson1974;Gavish1982,1983,1985;Gouveia1993,1995;GouveiaandAo1991;Hall1996;KershenbaumandBoorstyn1983;MalikandYu1993]availableforsolvingtheCMSTproblem.Theinstancesizesthatcanbesolvedbythesealgorithmstooptimality,inreasonableamountoftime,arestillfarfromthatofreal-timeinstances.
HeuristicsfortheCMSTproblemcanbeclassifiedintothreecategories:sav-ingsprocedures,constructionprocedures,andimprovementprocedures.EsauandWilliams[1966]gaveanefficientandwell-knownsavingsheuristicfortheCMSTproblem.SomeoftheotherheuristicsthatusesavingsproceduretoconstructthetreeincludeEliasandFerguson[1974],Gavish[1991],GavishandAltinkemer[1986],Kershenbaum[1974],Whitney[1970].Constructionprocedures[BoorstynandFrank1977;ChandyandRussell1972;Karnaugh1976;KershenbaumandChou1974;Martin1967;McGregorandShen1977;SchneiderandZastrow1982;SharmaandEl-Bardai1970]startwithanemptytreeandaddthebestedgeornodetogrowthetree.Improvementprocedures[EliasandFerguson1974;Frank
CapacitatedMinimumSpanningTreeProblem269
etal.1971;Karnaugh1976;Kershenbaumetal.1980;MalikandYu1993]startwithaninitialfeasiblesolution,usuallyobtainedbyrunningtheEsauandWilliams[1966]algorithm,andmakeimprovementsbyaddinganddeletingedgesaslongasimprovementsarepossible.Thereareotherheuristicsbasedontabusearchandsim-ulatedannealing[AartsandKorst1989;OsmanandChristofides1994;Sharaihaetal.1997].Formoredetailsontheseandotherheuristics,wereferthereadertothefollowingsurveypapers:Ambergetal.[1996]andVoß[2001]forfurtherin-formationonseveralwell-knownheuristics,andAhujaetal.[2001],Ambergetal.[1996],Domschkeetal.[1992],andGlover[1989,1990]forextensivebackgroundandcomparisonofseveralheuristicsbasedontabusearchtechniques.2.Preliminaries
Let|uv|denotethedistancebetweenverticesuandv.Lengthofanedgeisalsoitscost.Thetermspoints,nodes,andverticeswillbeusedinterchangeablyinthisarticle.Foragivenk,letOPTandAPPdenoteoptimalandapproximatesolutions,respectively,andletCoptandCappdenotetheirrespectivecosts.LetCmstandCSTdenotethecostsofanMSTandanoptimalSteinertree,respectively.
InarootedtreeT,lettvdenotethesubtreerootedatv.LetCTdenotethecostoftreeT.Letw(v)denotetheweightofvertexv,andletw(tv)denotethesumofvertexweightsinthesubtreerootedatv.FortheCMStTproblem,theweightofavertextheisnotinDisassumedtobe0.Byweightofasubtree,wemeanthesumofthevertexweightsinthatsubtree.WecalltheedgesincidentonrofaCMStTspokes.Bylevelofavertex,inatreeTrootedatr,wemeanthenumberoftreeedgesonitspathtor(alsoknownasdepth).
Bymetriccompletionofagivengraph(whoseedgesobeytriangleinequality),werefertoacompletegraph.Throughoutthisarticle,withoutlossofgenerality,weassumethatthemetriccompletionoftheinputgraphisavailable,andthattheweightsofverticesinV\\Darezero.AllouralgorithmsinthisarticlearefortheCMStTproblem—ageneralizationoftheCMSTproblem.Thefollowinglemmagivesalowerboundonthecostofanoptimalsolution.
1LEMMA2.1.Copt≥kv∈Vw(v)|rv|.PROOF.LettbethenumberofsubtreesconnectedtorinOPT.Letlbeone
suchsubtreeinOPTthatisconnectedtor.LetSlbethesetofverticesinl.LetClbethesumofthecostoftheedgesincidentontheverticesinl.Bytriangleinequality,
Cl≥max{|rv|}
v∈Sl
v∈Slw(v)|rv|≥w(v)
v∈Sl
v∈Slw(v)|rv|≥.
k
FortsubtreesconnectedtorinOPT,
Copt=
≥
tl=1v∈V
Cl
w(v)|rv|
.
k
270
3.CMStTAlgorithms
R.JOTHIANDB.RAGHAVACHARI
WefirstconstructaρST-approximateSteinertreeTspanningalltheverticesinD∪{r},andthenrootTattherootvertexr.Next,weprunesubtreesofweightatmostkinabottom-upfashion,andaddedgestoconnectrtotheclosestnodeineachoftheprunedsubtrees.Insimpleterms,webasicallycutTintosubtreesofweightatmostkandconnectthemtotherootvertex.
Itissafetoassumethatnodeshaveintegerweights.TheassumptionisnotrestrictiveasanyCMStTproblemwithrationalweightscanbeconvertedtoanequivalentproblemwithintegernodeweights.Theoptimalsolutionforthescaledproblemisidenticaltothatoftheoriginalproblem[AltinkemerandGavish1988].Sinceouralgorithmfortheuniformvertexweightscaseisquitecomplex,wefirstpresentthealgorithmforthegeneralcase(nonuniformvertexweights),whichwillhelpinaneasierunderstandingofouralgorithmfortheuniformvertexweightscase.Beforeweproceedtothealgorithms,wepresentthefollowingimportantlemma.
LEMMA3.1.ForagivengraphG=(V,E),asetofdemandsD⊆V,r∈V,andak,letTfbeafeasibleCMStTandlett1,t2,...,tmbethesubtreesconnectedtorinTf.Letw(tq)betheweightofaminimumweightsubtreetqconnectedtor.Foralli,ifthecostoftheedgeconnectingsubtreetitorisminimal,thenthecostCspofalltheedgesincidentonr(spokes)inTfisatmostk/w(tq)timesthecostofanoptimalsolution.
PROOF.Letbethesetofverticesint1,...,tm.Foralli,letvibethevertexintithroughwhichtiisconnectedtor.Recallthatedgerviisaspoke,andthatitisaminimalcostedgecrossingthecutbetweenrandti.Then,
v∈tw(v)|rv|
|rvi|≤i
v∈tiw(v)
v∈tiw(v)|rv|
.≤
w(tq)Thecostofthealltheedgesincidentonrisgivenby
Csp=
≤
mi=1
|rvi|
w(v)|rv|w(tq)
w(v)|rv|k
=×v∈D
w(tq)kk
×Copt(byLemma2.1).≤
w(tq)
v∈
3.1.NONUNIFORMVERTEXWEIGHTS.ThealgorithmgivenbelowoutputsafeasibleCMStTforagiveninstance,whoseedgesobeytriangleinequality.Notethatduringthecourseofthealgorithm,wereplacerealverticeswithdummyvertices
CapacitatedMinimumSpanningTreeProblem271
ofzeroweight.ThesedummyverticescanbethoughtofasSteinerpoints.Inthealgorithm,weusecitodenotethesubtreerootedatvertexv’sithchild,andpvtodenotev’sparent.
AlgorithmCMStT-NONUNIFORM
Input:ρST-approximateSteinertreeTrootedatr.
(1)Chooseamaximumlevelvertexv=rsuchthatw(tv)≥k.Ifthereexistsnosuchvertex,thenfor
eachsubtreescontainingadummyvertexandconnectedtor,replacetheSteineredgesincidentontheverticesinswiththeminimalcosttreeτspanningonlytheverticesins∩Dandr,andSTOP.
(2)Ifw(tv)=k,thenreplacetheSteinertreeedgesincidentontheverticesintvwiththeedgesof
aminimal-costtreeτspanningonlytheverticesintv∩D.Addanewedgeconnectingrtotheclosestvertexinτ.
(3)Elseif,forsomei,w(ci)≥k/2,thenreplacetheSteinertreeedgesincidentontheverticesin
ciwiththeedgesofaminimal-costtreeτspanningonlytheverticesinci∩D.Addanewedgeconnectingrtotheclosestvertexinτ.
(4)Elseifw(ci) finalsolution,addvandanedgeconnectingvtor. (5)Elsecollectasubsetsofsubtrees,eachofwhichisrootedatoneofv’schildren,suchthat k/2≤w(s)≤k.ReplacetheSteinertreeedgesincidentontheverticesinswiththeedgesofaminimal-costtreeτspanningonlytheverticesins∩D.Addanewedgeconnectingrtotheclosestvertexinτ.(6)Gotostep1. ItcanbeverifiedthatouralgorithmoutputsafeasibleCMStTforagivenk.THEOREM3.2.ForagivenCMStTinstance,Algorithmguaranteesanapproximationratioof(γρST+2). CMStT-NONUNIFORM PROOF.WeshowthatthecostofthetreeoutputbyAlgorithmCMStT-NONUNIFORMisatmostγρST+2timesthecostofanoptimalCMStT.TheinputtothealgorithmisaρST-approximateSteinertreeT. ItcanbeeasilyverifiedfromthealgorithmthatallthenewedgesaddedtotheoriginaltreeTareeithernewspokes,oredgesthatinterconnectverticeswithinthesubtreesforwhichthenewspokeswereadded.Inwhatfollows,weaccountforthecostofthenewspokesaddedtoT,followedbythecostofotheredgesinthefinalsolutionoutputbythealgorithm. Anewspoke,incidentonasubtree,isaddedtotheoriginalSteinertreeifandonlyiftheweightofthesubtreeitconnectsisatleastk/2.Noticethatthealgorithmoutputsatreewitheachsubtreeconnectedtorbeingdisjointandtheweightofeverysuchsubtree,forwhichanewspokewasadded,beingatleastk/2.LetCspbethecostofthespokesthatthealgorithm“adds”totheSteinertree.NotethatCspdoesnotincludethecostofthespokesthatarealreadyintheSteinertreethatwasgivenasinputtothealgorithm.ByLemma3.1, Csp≤2×Copt. Now,weaccountforthecostofotheredgesinthefinalsolution.TheseedgesareeithertheSteinertreeedgesortheedgesthatreplacedtheSteinertreeedges.WeshowthatthetotalcostofalltheseedgestogetherisatmostγtimesthecostoftheinitialSteinertree.Toprovethis,itsufficestoprovethatthecostoftheedges 272R.JOTHIANDB.RAGHAVACHARI thatreplacetheSteinertreeedgesisatmostγtimesthecostoftheSteinertreeedgesthatitreplaces.Foreverysubtreeformed,noticethatthealgorithmreplacedtheedgesoftheSteinertreespanningtheverticesinthatsubtreebytheedgesofanMSTspanningonlythenonzeroweightverticesinthatsubtree.SinceγwasdefinedtobetheinverseSteinerratio(ratioofthecostofanMSTversusthecostofanoptimalSteinertree),bySteinerratioargument,thecostoftheMSTspanningonlythenonzeroweightverticesinasubtreeisatmostγtimesthecostofanoptimalSteinertreespanningthenonzeroweightverticesinthatsubtree.Thus,wecanconcludethatthecostofthenewedgesisatmostγtimesthecostoftheρST-approximateSteinertreeedgesitreplaces.Thefinalcostofthetreeoutputbythealgorithmisgivenby Capp≤Csp+γρSTCST ≤2Copt+γρSTCopt≤(γρST+2)Copt. COROLLARY3.3.FortheCMStTproblemwithuniformvertexweights,Al-gorithmCMStT-NONUNIFORMwithlittlemodificationguaranteesa(ρST+2)-approximationratio. PROOF.Sincewearedealingwithuniformvertexweights,withoutlossofgenerality,wecanassumethattheyareofunitweight,andthuswecaneliminateStep.4fromAlgorithmCMStT-NONUNIFORM.Thereforenodummyverticesareintroducedbythealgorithm.Onceasubtreetofsizeatleastk/2isfound,insteadofreplacingtheSteinertreespanningtheverticesintwithaMSTspanningthenonzeroweightverticesint,wecanjustusetheedgesint,minustheedgethatconnectsttoitsparent,astheyare.Thiseliminatestheγfromthefinalratio.COROLLARY3.4.FortheCMSTproblem,AlgorithmCMStT-NONUNIFORMguaranteesa(γ+2)-approximationratio.Inparticular,forpointsinEuclideanandrectilinearplanes,itguaranteesaratioof3.1548and3.5,respectively.PROOF.SincetheMSTcostisalowerboundontheCMST,theCMStTalgorithm√withanMSTastheinputwillguaranteeanapproximationratioof(γ+2)being2/3and3/2intheEuclideanandrectilinearmetrics,respectively,whichcompletestheproof. 3.2.UNIFORMVERTEXWEIGHTS.AlthoughouralgorithmforuniformvertexweightscaseissimilartoAlgorithmCMStT-NONUNIFORMatthetoplevel,contrarytoexpectations,therearesomecomplicatedissuesthathavetobehandledinordertoobtainanapproximationratiostrictlylessthanρST+2.Fromouranalysisforthenonuniformvertexweightscase,wecanseethattheweightoftheminimumweightsubtreeconnectedtorplaysacrucialroleinthecalculationoftheapproximationratio.Anobviousheuristicistoprunesubtreesofweightascloseaspossibletok,sothattheratiodropsconsiderably.Wewillsoonseewhypruningsubtreesofweightstrictlygreaterthank/2ismoredifficultthanpruningsubtreesofweightgreaterthanorequaltok/2.Toovercomethedifficultyofpruningsubtreesofsizestrictlygreaterthank/2,weintroducetheconceptofX-trees,whichwedefinebelow.Wecallasubtree,tv,rootedatvertexvanX-tree,x,ifallofthefollowingproperties CapacitatedMinimumSpanningTreeProblem273 FIG.1.AnX-treewithk=100. aresatisfied(seeFigure1): k.—k Input:ρST-approximateSteinertreeTrootedatr,withvertexdegreesatmost5. (1)Chooseamaximumlevelvertexv=rsuchthattvisanon-X-treewithw(tv)≥k.Ifthereexists nosuchvertexthengotostep11. (2)Ifw(tv)=k,thenaddanewedgeconnectingrtotheclosestnodeintv.Removeedgevpvfrom T. (3)Elseif,forsomei,2k/3≤w(ci)≤k,thenaddanewedgeconnectingrtotheclosestnodein ci.RemovetheedgeconnectingvtocifromT. (4)Elseif,forsomeiandj(i=j),2k/3≤w(ci)+w(cj)≤k,thenreplaceedgesvciandvcjby aminimalcostedgeconnectingciandcj,mergingthetwosubtreesintoasingletrees.Addanewedgetoconnectrtotheclosestnodeins. (5)Elseif,forsomei,j,andz(i=j=z),2k/3≤w(ci)+w(cj)+w(cz)≤k,thenreplacethe Steinertreeedgesincidentontheverticesinci,cj,andczbyaminimal-costtreesspanningalltheverticesinci,cj,andcz(Figure2(a)).Addanewedgeto,connectrtotheclosestnodeins. 274R.JOTHIANDB.RAGHAVACHARI FIG.2.Illustrationof(a)Step5and(b)Step6. FIG.3.X-treewithinanX-tree. (6)Elseif,forsomei,j,andz(i=j=z),4k/3≤w(ci)+w(cj)+w(cz)≤2k,thendothe following: LetEibethesetofedgesincidentonverticesinci.WedefineEj(Ez)withrespecttocj(respectively,cz)analogously.Withoutlossofgenerality,letEjbethelow-costedgesetamongEi,Ej,andEz.UseDFSoncjtopartitiontheverticesincjintotwosetsg1andg2suchthatthetotalweightofverticesin(ci∪g1)∩Disalmostthesameasthetotalweightofverticesin(cz∪g2)∩D.Removealltheedgesincidentontheverticesinsubtreesci,cjandcz.Constructaminimalcostspanningtrees1comprisingtheverticesinciandg1.Similarly,constructaminimal-costspanningtrees2comprisingtheverticesinczandg2.Addnewedgestoconnectrtotheclosestnodesins1ands2. (7)Elseif,forsomeiandj(i=j),2k LetG1={E1,E2},G2={E3},andG3={E4,E5}bethreegroups.Outof{E1,E2,E3,E4,E5},doubletwolow-costedgesetssuchthattheybelongtodifferentgroups. CapacitatedMinimumSpanningTreeProblem275 FIG.4.PartitioningtheedgeswithinanX-tree. FIG.5.IllustrationofStep7(a). FIG.6.IllustrationofStep7(b). (a)IfEiandEjwerethetwoedgessetsthatweredoubled,withEiinG1andEjinG3, thenformthreeminimal-costsubtreess1,s2,ands3spanningtheverticesinxiandxjasfollows.Withoutlossofgenerality,letE2andE4bethetwolow-costedgesetsthatweredoubled(Figure5).Useshortcuttingtoforms1spanningallverticesintα1andasubsetofverticesintβ1,forms3spanningallverticesintβ2andasubsetofverticesintα2,andforms2withalltheleft-oververtices.Removeedgevpv.Sincek G2,thenformthreeminimal-costsubtreess1,s2,ands3spanningtheverticesinxiandxjasfollows.Withoutlossofgenerality,letE2andE3bethetwolow-costedgesetsthatweredoubled(seeFigure6).Fromtα2andtβ2findavertexwsuchthat|wr|isminimum.Withoutlossofgenerality,lettα2containw.Useshortcuttingtoforms3spanningalltheverticesinxjminustheverticesintβ2(seeFigure7).Notethatk/3 FIG.7.Pruningasubtreeofweightatleastk/3andatmostkfromanX-tree. (c)Addnewedgestoconnectrtotheclosestnodesins1,s2,ands3. Elseif,forsomeiandj(i=j),4k/3≤w(xi)+w(cj)<2k,dothefollowing. Letv1beamaximumlevelvertexinX-treexisuchthattv1isanX-treeitself.Recall,byProposition3.5,thatthereexisttwosubtreestα1andtβ1,connectedtov1suchthatk (8) (9) (10)(11) LEMMA3.6.AlgorithmCMStT-UNIFORMconsidersallthepossiblecasesforagivensubtreetv. PROOF.RecallthatweareworkingwithaρST-approximateSteinertreewithmaximumnodaldegreeatmost5.IfthesubtreetvfitsintooneofSteps2–6,thenthealgorithmwillsolvethecaseusingoneofthosesteps.Hence,fortherestoftheproof,wecanassumethatsubtreetvdoesnotfitintoanyofSteps2–6.SincetvisasubtreeofweightgreaterthankanddoesnotfitintoanyofSteps2–6,theremustbeatleastoneX-treeconnectedtov.Ascanbeseenfromthealgorithm,Steps7–9capturesallpos-siblecasesunderthissetting. THEOREM3.7.ForagivenCMStTinstanceonaLpplane,AlgorithmCMStT-3 ρ+).UNIFORMguaranteesanapproximationratioof(7ST52PROOF.WeshowthatthecostofthetreeoutputbyAlgorithmCMStT-UNIFORM isatmost(7ρ+3)timesthecostofanoptimalCMStT.Theinputtothealgorithm5ST2isaρST-approximateSteinertreeTwithmaximumnodaldegreeatmost5. Thealgorithm“adds”anewspoketothetreewheneveritprunesasubtreeofweightatleast2k/3.Therearecertainsituations(Steps6and11)wherethe CapacitatedMinimumSpanningTreeProblem277 algorithmaddsaspokeforprunedsubtreesofweightlessthan2k/3.Wecontinueouranalysisasifalloftheprunedsubtreeswereofweightatleast2k/3.Thissuppo-sitionmakestheanalysisofspokecostsimpler.Wewillsoonjustifythissupposition(inCases5and8)inamannerthatdoesnotaffecttheoverallanalysisinanyway.ThecostofthespokesthatwereaddedtotheinitialSteinertreeisgivenby Csp≤ 3 ×Copt2 byanargumentanalogoustothatprovingthecostofthespokesthatthealgorithmaddstotheinitialSteinertreeinTheorem3.2.Theaboveinequalityfollowsimmediatelyfromthefactthatanewspokeisaddedtothetreeifandonlyifthesubtreeitconnectstorisofweightatleast2k/3. Now,weaccountforthecostofotheredges—alltheedgesinthefinalsolution,exceptforthespokesaddedbythealgorithm—inthefinalsolution.Weshowthatthecostoftheseedgesisatmost7/5timesthecostoftheSteinertreeedgesthatthealgorithmstartedwith.Toprovethis,itsufficestoshowthatthecostoftheedgesthatreplacetheSteinertreeedgesisatmost7/5timesthecostoftheedgesthatarereplaced.Inwhatfollows,weshowthisbypresentingacase-by-caseanalysisdependinguponwhichstepofthealgorithmwasexecuted. Case1.Steps1,2,3,and10donotaddanynonspokeedges.TheweightofthesubtreesforwhichSteps1and2addsspokestothetreeisatleast2k/3. Case2.Theminimal-costedgeconnectingciandcjinStep4isatmostthesumofthetwoSteinertreeedgesthatconnectciandcjtov(bytriangleinequality).Hencenoadditionalcostisinvolved. Case3.InStep5,thecostofthetreesspanningalltheverticesinci,cj,andczisatmostthecostofthetreeobtainedbydoublingtheminimum-costedgeoutofthethreeSteinertreeedgesthatconnectthethreesubtreestov(seeFigure2(a)).Hence,wecanconcludethatthecostofthetreeconstructedinStep5isatmost4/3timesthecostoftheSteinertreeedgesitreplaces. Case4.InStep6,thetotalcostofthetreess1ands2spanningalltheverticesinci,cj,andczisatmostthetotalcostofthetreest1andt2obtainedbydoublingtheminimum-costedgesetoutofthethreeedgesetsthatareincidentontheverticesinci,cj,andcz,respectively(seeFigure2(b)).Hence,wecanconcludethatthecostofthetreeconstructedinStep6isatmost4/3timesthecostoftheSteinertreeedgesitreplaces. Case5.Step7formsthreesubtreess1,s2,ands3fromX-treesxiandxj.Sinces1,s2,ands3canbeformedbydoublingtwolow-costedgesets(belongingtotwodifferentgroups)outofthefivepossibleedgesetsandshortcutting,wecanconcludethatthecostofthesubtreess1,s2,ands3constructedinStep7isatmost7/5timesthecostoftheSteinertreeedgesitreplaces. AccountingforthecostofthespokesaddedtotheSteinertreerequiresthateachsubtreeprunedfromtheSteinertreebeofweightatleast2k/3.WealreadyprovedthatthecostofthespokesaddedtotheSteinertreeisatmost3/2timesthecostofanoptimalsolution.Withoutlossofgenerality,therequirementthateachprunedsubtreeisofweightatleast2k/3canbeinterpretedasthatof“charging”thespokecostincidentonasubtreetoatleast2k/3vertices.Noticethatthisinterpretationisvalidonlyifthespokeconnectingthesubtreetotherootisofminimalcost(risconnectedtotheclosestnodeinthesubtree). 278R.JOTHIANDB.RAGHAVACHARI Step7(a)ofthealgorithmconstructsthreesubtreess1,s2,ands3,eachcontainingatleast2k/3vertices.Thisensuresthatthereareatleast2k/3verticestowhicheachofthesesubtreescanchargetheirspokecost.ThisisnotthecasewithStep7(b)ofthealgorithm.Ascanbeseen,subtrees3mightbeofweightlessthan2k/3.Sinces2containsatleast2k/3verticesandw(s2)+w(s3)≥4k/3,andwisavertexinxjsuchthat|wv|isminimum,wecanalwayschargethespokecostsofs2ands3toatleast4k/3vertices.Hence,ourinitialassumptionthateveryprunedsubtreeisofweightatleast2k/3doesnotaffecttheanalysissincethereareatleast2k/3verticesforeveryspoketocharge. Case6.TheanalysesforSteps8and9aresimilartothatforStep6(Case4).Case8.Step11prunesonesubtreeoffX-treex.Thecostofthespoke|rw|toconnecttαtorcanbechargedtoalltheverticesintheX-treexasperthefollowingargument.AfterdisconnectingtαfromtheX-tree,weareleftwithasubtreeofw(x)−w(tα) Capp≤ 73ρSTCST+Copt52 37 ρST+Copt.≤52 COROLLARY3.8.FortheCMSTproblemintheLpplanewithuniformvertex weights,AlgorithmCMStT-UNIFORMguaranteesa2.9-approximationratio.3.3.UNITVERTEXWEIGHTSWITHk=3,4.TheCMSTproblemispolynomialtimesolvableifallverticeshaveunitweights,andk=2[GareyandJohnson1979].Weshowthatanoptimalsolutionfork=2isa2-approximationfork=3,4.Letopt2,opt3,andopt4betheoptimalcostsfork=2,k=3,andk=4,respectively.THEOREM3.9.GivenaundirectedgraphG=(V,E)withunitvertexweights,r∈V,andk=3or4,anoptimalsolutionfortheCMSTproblemwithk=2isa2-approximationfortheCMSTproblemwithk=3,4. PROOF.Weobtainthefollowinginequalitiesfromthefactthatonecouldobtainafeasiblesolutionfork=2bydoublingtheedgesofanoptimalsolutionfork=3,4: opt2≤2×opt3 and opt2≤2×opt4. Ifweweretouseopt2asafeasiblesolutionfork=4,then Ratio= opt2opt2≤=2.opt4opt2/2Usingthesameargument,wecanconcludethatopt2/opt3≤2. CapacitatedMinimumSpanningTreeProblem279 TABLEI.COMPARISONOFOURRATIOSWITHTHOSEOFALTINKEMERANDGAVISH[1988]FORTHE BUDGETEDCMSTPROBLEM α124...∞UniformVertexWeightsinLpPlaneOurratioAG’sratio2211+α2−k+α321.5...123−k22.5−k22.25−k...2NonuniformVertexWeightsinEuclideanPlaneOurratioAG’sratio222√+2+αα33.1552.1551.655...1.155432.5...24.TheBudgetedCMSTProblem Inthissection,weshowtheeffectsofusingMSTcostasalowerboundfortheCMSTproblem.Forthispurpose,wetrytocompareouralgorithmsfortheCMSTproblemwiththoseofAltinkemerandGavish[1988].InAltinkemerandGavish[1988],theapproximationratiosaredominatedbytheMSTcost,whilethatisnotthecasewithouralgorithms. WeconsiderarelaxedversionoftheCMSTproblem,thebudgetedCMSTproblem,inwhichacompromisecanbemadeonthecapacityconstraintk.Inthisversion,foragivenk,theweightsofthesubtreesconnectedtorcouldbeuptoαk,whereα≥1.ThisgivesflexibilitywhenthecostoffinalsolutionhastobebelowacertainbudgetB,Cmst THEOREM4.1.ForagivenCMSTinstanceandak,AlgorithmCMStT-NONUNIFORMfindsaCMST,withtheweightofeverysubtreeconnectedtorbeing 2 atmostαk,whosecostisatmostγ+αtimesthecostofanoptimalsolutiontothegivenproblem. PROOF.TheproofissimilartotheoneforTheorem3.2. THEOREM4.2.ForagivenCMSTinstanceintheLpplanewithuniformvertexweights,andak,AlgorithmCMStT-NONUNIFORMfindsaCMST,withtheweightof 2 everysubtreeconnectedtorbeingatmostαk,whosecostisatmost1+αtimesthecostofanoptimalsolutiontothegivenproblem. PROOF.Withoutlossofgenerality,wecanassumethattheverticesareofunitweightandscalekaccordingly.Sincetheverticesareofunitweight,Step4oftheAlgorithmCMST-NONUNIFORMwillneverbeexecuted,andthustheconceptofdummyorSteinerverticesneverhavetobeintroduced.ThisdirectlymeansthattheedgeswithineverysubtreeconnectedtorareMSTedges.TherestoftheprooffollowsalongthesamelineasthatforTheorem3.2. TableIshowsthecomparisonofourratioswiththoseofAltinkemerandGavish[1988]forspecialcasesofthebudgetedCMSTproblem(AGdenotesAltinkemerandGavish). 280R.JOTHIANDB.RAGHAVACHARI FIG.8.Atightexamplefor2-approximationratio. 5.Conclusion Inthisarticle,wepresentedapproximationalgorithmsfortheCMStTproblem.Thisdirectlytranslatesintoimprovedapproximationguaranteesforthewell-studiedCMSTproblem.OurresultsfortheCMSTproblemareanimprovementoverthe15-year-oldcurrentbestapproximationsfortherespectiveproblems. Ourratiosare,certainly,nottight.Webelievethatthereisroomforimprove-ment,atleastfortheCMSTproblemwithuniformvertexweights,forwhichweobtainedaratioof2.9.ThecostofanoptimalCMSTcanbelowerboundedbyoneofthefollowingtwoquantities:(i)theMSTcostand(ii)thespokelowerbound(Lemma2.1).ConsiderFigure8,whichcontainsα2kpointsinaunit-spacedgrid.MSTcostofthepointsinthegridaloneisα2k−1.Letkbethedistancebetweenrandtheclosestnodeinthegrid.Forcapacityconstraintk,thecostofanoptimalsolutionwouldbe2α2k−α2,whereastheMSTcostwouldbe(α2+1)k−1andthespokelowerboundwouldbeα2k.Thisshowsthat,withthecurrentlowerbounds,onecannotgetaratioanybetterthan2.ItwouldbeinterestingtoseewhetherwecouldfindaunifiedlowerboundbycombiningtheMSTcostandthespokecostinasomeway,insteadofjustanalyzingthemseparately.Wedonotseeareasonwhyourofratioof2.9cannotbeimprovedto2. ACKNOWLEDGMENTS. WethankR.ChandrasekaranandOvidiuDaescuforuseful discussions. REFERENCES AARTS,E.,ANDKORST,J.1989.SimulatedAnnealingandBoltzmanMachines.Wiley,Chichester,U.K.AHUJA,R.,ORLIN,J.,ANDSHARMA,D.2001.Acompositeneighborhoodsearchalgorithmforthecapacitatedminimumspanningtreeproblem.Oper.Res.Letters31,185–194. ALTINKEMER,K.,ANDGAVISH,B.1988.Heuristicswithconstanterrorguaranteesforthedesignoftreenetworks.Manage.Sci.34,331–341. AMBERG,A.,DOMSCHKE,W.,ANDVOß,S.1996.Capacitatedminimumspanningtrees:Algorithmsusingintelligentsearch.Comb.Opt.:Theor.Pract.1,9–39. BOORSTYN,R.,ANDFRANK,H.1977.Large-scalenetworktopologicaloptimization.IEEETrans.Comm.25,29–47. CHANDY,K.,ANDLO,T.1973.Thecapacitatedminimumspanningtree.Networks3,173–181. CHANDY,K.,ANDRUSSELL,R.1972.Thedesignofmultipointlinkagesinateleprocessingtreenetwork.IEEETrans.Comp.21,1062–1066. DOMSCHKE,W.,FORST,P.,ANDVOß,S.1992.Tabusearchtechniquesforthequadraticsemi-assignmentproblem.InNewDirectionsforOperationsResearchinManufacturing.Springer,Berlin,Germany,389–405. ELIAS,D.,ANDFERGUSON,M.1974.Topologicaldesignofmultipointteleprocessingnetworks.IEEETrans.Comm.22,1753–1762. ESAU,L.,ANDWILLIAMS,K.1966.Onteleprocessingsystemdesign.IBMSys.J.5,142–147. FRANK,H.,FRISCH,I.,SLYKE,R.V.,ANDCHOU,W.1971.Optimaldesignofcentralizedcomputerdesignnetwork.Networks1,43–57. CapacitatedMinimumSpanningTreeProblem281 GAREY,M.,ANDJOHNSON,D.1979.ComputersandIntractability:AGuidetotheTheoryofNP-Completeness.W.H.Freeman,SanFrancisco,CA. GAVISH,B.1982.Topologicaldesignofcentralizedcomputernetworks—formulationsandalgorithms.Networks12,355–377. GAVISH,B.1983.Formulationsandalgorithmsforthecapacitatedminimaldirectedtreeproblem.J.Assoc.Comput.Mach.30,118–132. GAVISH,B.1985.Augmentedlagrangeanbasedalgorithmsforcentralizednetworkdesign.IEEETrans.Comm.33,1247–1257. GAVISH,B.1991.Topologicaldesignoftelecommunicationnetworks—localaccessdesignmethods.Ann.Oper.Res.33,1,17–71. GAVISH,B.,ANDALTINKEMER,K.1986.Parallelsavingsheuristicsforthetopologicaldesignoflocalaccesstreenetworks.InProceedingsoftheIEEEINFOCOM.130–139.GLOVER,F.1989.Tabusearch—parti.ORSAJ.Comput.1,190–206.GLOVER,F.1990.Tabusearch—partii.ORSAJ.Comput.2,4–32. GOEMANS,M.,ANDWILLIAMSON,D.1995.Ageneralapproximationtechniqueforconstrainedforestproblems.SIAMJ.Comput.24,296–317. GOUVEIA,L.1993.Acomparisonofdirectedformulationsforthecapacitatedminimalspanningtreeproblem.Telecomm.Syst.1,51–76. GOUVEIA,L.1995.A2nconstraintformulationforthecapacitatedminimalspanningtreeproblem.Oper.Res.43,130–141. GOUVEIA,L.,ANDAO,J.P.1991.Dynamicprogrammingbasedheuristicsforthetopologicaldesignoflocalaccessnetworks.Ann.Oper.Res.33,305–327. HALL,L.1996.Experiencewithacuttingplaneapproachforthecapacitatedspanningtreeproblem.INFORMSJ.Comput.8,219–234. HASSIN,R.,RAVI,R.,ANDSALMAN,F.2000.Approximationalgorithmsforcapacitatednetworkdesignproblems.InProceedingsoftheWorkshoponApproximationAlgorithmsforCombinatorialOptimization(APPROX).167–176. JOTHI,R.,ANDRAGHAVACHARI,B.2004a.Approximationalgorithmsforthecapacitatedminimumspanningproblemanditsvariantsinnetworkdesign.InProceedingsofthe31stInternationalColloquiumonAutomata,LanguagesandProgramming(ICALP).805–818. JOTHI,R.,ANDRAGHAVACHARI,B.2004b.Survivablenetworkdesign:Thecapacitatedminimumspan-ningnetworkproblem.InformProcess.Lett.91,4,183–190. KARNAUGH,M.1976.Anewclassofalgorithmsformultipointnetworkoptimization.IEEETrans.Comm.24,500–505. KERSHENBAUM,A.1974.Computingcapacitatedminimalspanningtreesefficiently.Networks4,299–310. KERSHENBAUM,A.,ANDBOORSTYN,R.1983.Centralizedteleprocessingnetworkdesign.Networks13,279–293. KERSHENBAUM,A.,BOORSTYN,R.,ANDOPPENHEIM,R.1980.Second-ordergreedyalgorithmsforcentralizedteleprocessingnetworkdesign.IEEETrans.Comm.28,1835–1838. KERSHENBAUM,A.,ANDCHOU,W.1974.Aunifiedalgorithmfordesigningmultidropteleprocessingnetworks.IEEETrans.Comm.22,1762–1772. MALIK,K.,ANDYU,G.1993.Abranchandboundalgorithmforthecapacitatedminimumspanningtreeproblem.Networks23,525–532. MARTIN,J.1967.DesignofReal-TimeComputerSystems.PrenticeHall,EnglewoodCliffs,NJ. MCGREGOR,P.,ANDSHEN,D.1977.Networkdesign:Analgorithmfortheaccessfacilitylocationproblem.IEEETrans.Comm.25,61–73. MONMA,C.,ANDSURI,S.1992.Transitionsingeometricminimumspanningtrees.Disc.Comput.Geom.8,265–293. OSMAN,I.,ANDCHRISTOFIDES,N.1994.Capacitatedclusteringproblemsbyhybridsimulatedannealingandtabusearch.Intl.Trans.Oper.Res.1,317–336. PAPADIMITRIOU,C.1978.Thecomplexityofthecapacitatedtreeproblem.Networks8,217–230. ROBINS,G.,ANDSALOWE,J.1995.Low-degreeminimumspanningtrees.Disc.Comput.Geom.14,151–166. SALMAN,F.,CHERIYAN,J.,RAVI,R.,ANDSUBRAMANIAN,S.1997.Buy-at-bulknetworkdesign:Ap-proximatingthesingle-sinkedgeinstallationproblem.InProceedingsofthe8thACM-SIAMSymposiumonDiscreteAlgorithms(SODA).619–628. SCHNEIDER,G.,ANDZASTROW,M.1982.Analgorithmforthedesignofmultilevelconcentratornet-works.Comput.Netw.6,563–581. 282R.JOTHIANDB.RAGHAVACHARI SHARAIHA,Y.,GENDREAU,M.,LAPORTE,G.,ANDOSMAN,I.1997.Atabusearchalgorithmforthecapacitatedshortestspanningtreeproblem.Networks29,161–171. SHARMA,R.,ANDEL-BARDAI,M.1970.Suboptimalcommunicationsnetworksynthesis.InProceedingsoftheIEEEInternationalConferenceonCommunications.19.11–19.16. VOß,S.2001.Capacitatedminimumspanningtrees.InEncyclopediaofOptimization.Kluwer,Boston,MA,225–235. WHITNEY,V.1970.Astudyofoptimalfileassignmentandcommunicationnetworkconfigurationinremoteaccesscomputermessageprocessingandcommunicationssystems.Ph.D.Dissertation.UniversityofMichigan,AnnArbor,MI. RECEIVEDMARCH 2005;ACCEPTEDAPRIL2005 ACMTransactionsonAlgoritms,Vol.1,No.2,October2005. 因篇幅问题不能全部显示，请点此查看更多更全内容