Fast approximation schemes for Euclidean multi-connectivity problems

Multi-ConnectivityProblems

(ExtendedAbstract)

ArturCzumaj

andAndrzejLingas

DepartmentofComputerandInformationScience,NewJerseyInstituteofTechnology,

Newark,NJ07102-1982,USA.czumaj@cis.njit.edu

DepartmentofComputerScience,LundUniversity,Box118,S-22100Lund,Sweden.

Andrzej.Lingas@cs.lth.seAbstract.Wepresentnewpolynomial-timeapproximationschemes(PTAS)forseveralbasicminimum-costmulti-connectivityproblemsingeometricalgraphs.Wefocusonlowconnectivityrequirements.Eachofourschemeseithersignifi-cantlyimprovesthepreviouslyknownuppertime-boundoristhefirstPTASfortheconsideredproblem.

Weprovidearandomizedapproximationschemeforfindingabiconnectedgraphspanningasetofpointsinamulti-dimensionalEuclideanspaceandhavingtheexpectedtotalcostwithinoftheoptimum.Foranyconstantdimensionand,ourschemerunsintime.ItcanbeturnedintoLasVegasonewith-outaffectingitsasymptotictimecomplexity,andalsoefficientlyderandomized.Theonlypreviouslyknowntrulypolynomial-timeapproximation(randomized)schemeforthisproblemrunsinexpectedtimeinthesimplestplanarcase.Theefficiencyofourschemereliesontransformationsofnearlyoptimallowcostspecialspannersintosub-multigraphshavinggoodde-compositionandapproximationpropertiesandasimplesubgraphconnectivitycharacterization.Byusingmerelythespannertransformations,weobtainaveryfastpolynomial-timeapproximationschemeforfindingaminimum-cost-edgeconnectedmultigraphspanningasetofpointsinamulti-dimensionalEuclidean

.space.Foranyconstantdimension,,and,thisPTASrunsintime

Furthermore,byshowingalow-costtransformationofa-edgeconnectedgraphmaintainingthe-edgeconnectivityanddevelopingnoveldecompositionprop-erties,wederiveaPTASforEuclideanminimum-cost-edgeconnectivity.Itissubstantiallyfasterthanthatpreviouslyknown.

Finally,byextendingourtechniques,weobtainthefirstPTASfortheproblemofEuclideanminimum-costSteinerbiconnectivity.Thisschemerunsintime

foranyconstantdimensionand.Asabyproduct,wegetthefirst

knownnon-trivialupperboundonthenumberofSteinerpointsinanoptimalsolutiontoaninstanceofEuclideanminimum-costSteinerbiconnectivity.

1Introduction

Multi-connectivitygraphproblemsarecentralinalgorithmicgraphtheoryandhavenumerousapplicationsincomputerscienceandoperationresearch[2,10,22].They

arealsoveryimportantinthedesignofnetworksthatariseinpracticalsituations[2,10].Typicalapplicationareasincludetelecommunication,computerandroadnetworks.Lowdegreeconnectivityproblemsforgeometricalgraphsintheplanecanoftencloselyapproximatesuchpracticalconnectivityproblems(see,e.g.,thediscussionin[10,22]).

Inthispaper,weprovideathoroughtheoreticalstudyoftheseproblemsinEu-clideanspace(i.e.,forgeometricalgraphs).Weconsiderseveralbasicconnectivityproblemsofthefollowingform:foragivensetofpointsintheEuclideanspace,findaminimum-costsubgraphofacompletegraphonthatsatisfiesapriorigivencon-nectivityrequirements.ThecostofsuchasubgraphisequaltothesumoftheEuclideandistancesbetweenadjacentvertices.

Themostclassicalproblemweinvestigateisthe(Euclidean)minimum-cost-vertexconnectedspanningsubgraphproblem.WearegivenasetofpointsintheEu-andtheaimistofindaminimum-cost-vertexconnectedgraphspan-clideanspace

ningpointsin(i.e.,asubgraphofthecompletegraphon).Bysubstitutingtherequirementof-edgeconnectivityforthatof-vertexconnectivity,weobtainthecor-responding(Euclidean)minimum-cost-edgeconnectedspanningsubgraphproblem.Wetermthegeneralizationofthelatterproblemwhichallowsforparalleledgesintheoutputgraphspanningasthe(Euclidean)minimum-cost-edgeconnectedspanningsub-multigraphproblem.

Theconceptofminimum-cost-connectivitynaturallyextendstoincludethatofEuclideanSteiner-connectivitybyallowingtheuseofadditionalvertices,calledSteinerpoints.Theproblemof(Euclidean)minimum-costSteiner-vertex-(or,-edge-)con-nectivityistofindaminimum-costgraphonasupersetoftheinputpointsetinwhichis-vertex-(or,-edge-)connectedwithrespectto.For,itissimplythefamousSteinerminimaltree(SMT)problem,whichhasbeenveryextensivelystudiedintheliterature(see,e.g.,[11,16]).

-hardwhenrestrictedtoSincealltheaforementionedproblemsareknowntobe

eventwo-dimensionsfor[8,18],wefocusonefficientconstructionsofgoodap-proximations.Weaimatdevelopingapolynomial-timeapproximationscheme,aPTAS.Thisisafamilyofalgorithmssuchthat,foreachfixed,runsintime

-approximation[15].polynomialinthesizeoftheinputandproducesa

Previouswork.Despitethepracticalrelevanceofthemulti-connectivityproblemsfor

geometricalgraphsandthevastamountofpracticalheuristicresultsreported(see,e.g.,[9,10,22,23])verylittletheoreticalresearchhasbeendonetowardsdevelopingeffi-cientapproximationalgorithmsfortheseproblems.Thiscontrastswiththeveryrichandsuccessfultheoreticalinvestigationsofthecorrespondingproblemsingeneralmetricspacesandforgeneralweightedgraphs(see,e.g.,[10,12,15,17]).Evenforthesimplest(andmostfundamental)problemconsideredinourpaper,thatoffindingaminimum-costbiconnectedgraphspanningagivensetofpointsintheEuclideanplane,foralongtimeobtainingapproximationsachievingbetterthana

,thealgorithmrunsinexpectedtime.Notethatplaysalargeroleintherunningtimeoftheseschemes.Infact,there-sultfrom[6]impliesthatforevery,evenfornoPTASexistsunless.Thus,theproblemoffindingaminimum-costbiconnectedspanning

)eveninthemetriccase.Hence,subgraphdoesnothaveaPTAS(unless

ourrestrictiontoEuclideangraphsinlowdimensionsplaysanessentialroleintheseschemes.

Arelated,butsignificantlyweakerresulthasbeenalsopresentedin[5].HereanoptimalsolutiontotheproblemwithoutallowingSteinerpointsisapproximatedtoanarbitrarilyclosedegreeviatheinclusionofSteinerpoints.

WhenSteinerpointsareallowedintheminimum-costSteiner-vertex-(or-edge-)

,i.e.,fortheconnectivityproblem,theonlynon-trivialresultsareknownfor

minimumSteinertreeproblem(SMT).Inthebreakthroughpaper[3],AroradesignedaPTASforSMTforallconstants.Mitchellindependentlyobtainedasimilarresultfor

[19].SoonafterRaoandSmith[20]offeredasignificantlyfasterPTASforSMTrunningintimeforaconstant.For,theonlyresultweareawareofisa

and,runsinexpectedtime.Thecorrespondingschemein[6]requires

timewhenandforanyconstant.

Furthermore,wepresentaseriesofnewstructuralresultsaboutminimum-costbi-connectedEuclideanSteinergraphs,e.g.,adecompositionofaminimum-costbicon-nectedSteinergraphintominimalSteinertrees.WeusetheseresultstoderivethefirstPTASfortheminimum-costSteinerbiconnectivityandSteinertwo-edgeconnectivity

.Asproblems.Foranyconstantand,ourschemerunsinexpectedtime

abyproductoftheaforementioneddecomposition,wealsoobtainthefirstknownnon-trivialupperboundontheminimumnumberofSteinerpointsinanoptimalsolutionto

.an-pointinstanceofEuclideanminimum-costSteinerbiconnectivity,whichis

Techniques.TheonlytwoknownPTASapproachestoEuclideanminimum-cost-vertex-(or,-edge-)connectivity(see[5,6])arebasedondecompositionsof-connected

EuclideangraphscombinedwiththegeneralframeworkproposedrecentlybyArora[3]fordesigningPTASforEuclideanversionsofTSP,MinimumSteinerTree,Min-CostPerfectMatching,-TSP,etc.(ForanotherrelatedframeworkforgeometricPTASsee[19].)IncontrasttoallpreviousapplicationsofArora’sframeworkusingSteinerpointsintheso-calledpatchingprocedures[3,5],apatchingmethodfreeofSteinerpointsisgiven[6].(Steinerpointsofdegreeatleastthreearedifficulttoremovefor-connectivitywhen.ThisshouldbecomparedtotheproblemsconsideredbyArora[3]andRaoandSmith[20]wheretheoutputgraphshaveverysimpleconnectiv-itystructure.)Thisdisallowancein[6]makesithardtoprovestrongglobalstructuralpropertiesofcloseapproximationswithrespecttoagivengeometricpartition.

StructuraltheoremsinArora’sframeworktypicallyasserttheexistenceofarecur-sivepartitionofaboxcontainingtheinputpoints(perturbedtonearestgridpoints)intocubessuchthattheoptimalsolutioncanbecloselyapproximatedbyasocalled

-lightsolutioninwhich,foreverycube,thereareveryfewedgescrossingitsboundaries.Thestructuraltheoremin[6]yieldsonlyweakerstructuralpropertiesofapproximatesolutions(-graynessand-blueness)whichboundsolelythenumberofcrossingsbetweenthecubeboundariesandtheedgeshavingexactlyoneendpointwithinthecube.Thatboundisconstantfor“shortedges”(i.e.,edgeshavinglengthwithinaconstantfactoroftheside-lengthofthecube)anditis

for“longedges”(assumingthat,,andareconstant).Furthermore,mostofthecrossingsarelocatedinoneofprespecifiedpoints.Theweakerstructuralproperties

edgeshavingexactly(especiallythefactthattheremightbeasmanyas

oneendpointinacubeinthepartition)leadtothehightimecomplexityofthemaindynamicprogrammingprocedureinthePTASpresentedin[6].

WetakeanovelapproachinordertoguaranteestrongerstructuralpropertiesofapproximatesolutionsdisallowingSteinerpoints.Ourapproachispartlyinspiredbytherecentuseofspannerstospeed-upPTASforEuclideanversionsofTSPbyRaoand

,weareabletoproveasubstantiallystrongerstructuralSmith[20].Ineffect,for

property(-local-lightness,seeTheorem3.1)thanthatin[6].Ityieldsaconstantupperboundonthenumberoflongedgeswithexactlyoneendpointinacubeinthepartitionprovidedthatandareconstant.

Ourproofreliesonaseriesoftransformationsofa-spannerfortheinputpointset,havinglowcostandthesocalledisolationproperty[1],intoan-locally-light-edgeconnectedmultigraphspanningtheinputsetandhavingnearlyoptimalcost.Withoutanyincreaseinthecost,incase,theaforementionedmultigraphisefficientlytransformedintoabiconnectedgraphspanningtheinputpointset.Fur-thermore,forthepurposeofdynamicprogramming,wesucceedtouseamoreefficient

thanthatusedin[5,6].subgraphconnectivitycharacterizationincase

Byusingmerelytheaforementionedspannertransformations,wealsoobtainthefastrandomizedPTASforfindingaminimum-cost-edgeconnectedmultigraphspan-ningasetofpointsinamulti-dimensionalEuclideanspace.

Itseemsunlikelythatacost-efficienttransformationofa-edgeconnectedmulti-graphintoa-edgeconnectedgraphonthesamepointsetexists.Forthisreason,incaseof-edgeconnectivity,weconsideranarbitrary-edgeconnectedgraphonthein-putpointsetinsteadofaspanner,andderiveaseriesofcost-efficienttransformationsoftheformerintoan-locally-light-edgeconnectedgraphontheinputset.Thetransfor-mationsyieldthefastestknownrandomizedPTASforEuclideanminimum-cost-edgeconnectivity.

Ourinvestigationsofspannerswiththeisolationproperty,theexplicituseofmulti-graphsinsteadofgraphs,andtheproofthatnearlyoptimal,lowcostspannerspossess-ingtheisolationpropertyinduce-locally-lightsub-multigraphshavinggoodapproxi-mationpropertiesarethemainsourcesoftheefficiencyoftheapproximationschemesforEuclideanminimum-costconnectivityproblems(withoutSteinerpoints)presentedinthispaper.

ByextendingtheaforementionedtechniquestoincludeSteinerpoints,derivingthedecompositionofaminimum-costbiconnectedSteinergraphintominimalSteinertrees,andusingthegeneralizationof-spannertoincludeSteinerpointscalled-banyansin[20,21],weobtainthefirstPTASforminimum-costSteinerbiconnectivityandSteinertwo-edgeconnectivity.

Organizationofthepaper.Section2providesbasicterminologyusedinourapproxi-mationschemes.InSection3weoutlineournewPTASforEuclideanminimum-costbiconnectivity.Section4sketchesthePTASforEuclideanminimum-cost-edgecon-nectivityinmultigraphs.InSection5wederiveourPTASforEuclideanminimum-cost-edgeconnectivityingraphs.Section6presentsthePTASforminimum-costSteinerbiconnectivityandSteinertwo-edgeconnectivity.Duetospacelimitationsmostofourtechnicalclaimsandtheirproofsarepostponedtothefullversionofthepaper.

2Definitions

Weconsidergeometricalgraphs.Ageometrical(multi-)graphonasetofpointsin

isaweighted(multi-)graphwhosesetofverticesisexactlyandforwhichthecostofanedgeistheEuclideandistancebetweenitsendpoints.The(total)costofthe(multi-)graphisthesumofthecostsofitsedges.A(multi-)graphonspansifitisconnected(i.e.,thereisapathinconnectinganytwopointsin).Asin[3,5,6,20],weallowedgestodeviatefromstraight-linesegmentsandspecifythemasstraight-linespaths(i.e.,pathsconsistingofstraight-linesegments)connectingtheendpoints.Thisrelaxationenablestheedgestopassthroughsomeprespecifiedpoints

(calledportals)wheretheymaybe“bent.”Whenalledgesarestraight-linesegments,iscalledastraight-linegraph.Foramultigraph,thegraphinducedbyisthegraphobtainedbyreducingthemultiplicityofeachedgeoftoone.

.WeshalldenotethecostoftheminimumspanningtreeonapointsetbyMST

A-spannerofasetofpointsinisasubgraphofthecompletestraight-linegraph

thelengthoftheshortestpathfromtoinonsuchthatforanytwopoints

thespannerisatmosttimestheEuclideandistancebetweenand[1].

ROOTTLBLBRTRFig.1.Dissectionofaboundingcubein(left)andthecorresponding-arytree(right).Inthetree,thechildrenofeachnodeareorderedfromlefttoright:Top/Leftsquare,Bottom/Leftsquare,Bottom/Rightsquare,andTop/Rightsquare.

Wehierarchicallypartitionthespaceasin[3].Aboundingboxofasetofpointsinisasmallest-dimensionalaxis-parallelcubecontainingthepointsin.A(-ary)dissection[3](seeFigure1)ofasetofpointsinacubeinistherecursivepartitioningofthecubeintosmallersub-cubes,calledregions.Eachregionofvol-umeisrecursivelypartitionedintoregions.A-arytree(foragiven-arydissection)isatreewhoserootcorrespondsto,andwhoseothernon-leafnodescorrespondtotheregionscontainingatleasttwopointsfromtheinputset(see

regionsFigure1).Foranon-leafnodeofthetree,thenodescorrespondingtothe

partitioningtheregioncorrespondingto,arethechildrenofinthetree.

Forany-vector,whereallareintegers,the-shifteddissection[3,6]ofasetofpointsinthecubeinisthedissectionofthe

inthecubeinobtainedfrombytransformingeachpointset

to.Arandomshifteddissectionofasetofpointsinacubeinisan-shifteddissectionofwithandtheelementschosen

.independentlyanduniformlyatrandomfrom

Acrossingofanedgewitharegionfacetofside-lengthinadissectioniscalledrelevantifithasexactlyoneendpointintheregionanditslengthisatmost

exactlyoneendpointintheregion.Agraphis-light[3,20,6]withrespecttoashifteddissectionifforeachregioninthedissectionthereareatmostedgescrossinganyofitsfacets.(Itisimportanttounderstandthedifferencebetweenthesetwolatternotions.)

-dimensionalregionfacetisanAn-regularsetofportalsina

orthogonallatticeofpointsinthefacetwherethespacingbetweentheportalsis

(cf.[3]).Ifagraphis-locally-lightandforeachfacetinany

regioneveryedgecrossesthroughoneoftheportalsinthefacetthenthegraphiscalled-locally-light.

3AlgorithmforEuclideanbiconnectivity

Inthissectionwesketcharandomizedalgorithmthatfindsabiconnectedgraphspan-ningasetofpointsinwhosecostisatmosttimesoftheminimum.Wespecifyhereonlyakeylemmaandthestructuraltheoremanddeferthedetaileddescriptionofthealgorithmanditsanalysistothefullversionofthepaper.

Ouralgorithmstartsbyfindingasmallestboundingboxfortheinputpointsetrescalingtheinputcoordinatessotheboundingboxisoftheform

timestheside-lengthoftheregionthathavepreciselyone

endpointwithintheregionis.

Combiningthislemma,withseverallemmasthatdescribegraphtransformationsreducingthenumberofcrossingsoftheboundariesofaregioninthedissectionbyshortedges,weobtainthefollowingstructuraltheorem.

beanypositiverealsandletbeanypositiveinteger.Next,letTheorem3.1.Let

bea-spannerforawell-roundedsetofpointsinthatsatisfiesthe-isolationpropertywithconstant,,,andhasedgeswhosetotalcostequals.Chooseashifteddissectionuniformlyatrandom.Thenonecanmodifytoagraphspanningsuchthat

–

is-locally-lightwithrespecttotheshifteddissectionchosen,where

,and

–thereexistsa-edgeconnectedmultigraphwhichisaspanningsubgraphofwithpossibleparalleledges(ofmultiplicityatmost),whoseexpected(overthechoiceoftheshifteddissection)costisatmost

therunningtimeis.Thealgorithmcan

beturnedintoaLasVegasonewithoutaffectingthestatedasymptotictimebounds.

Althoughwehaveusedmanyideasfrom[6]inthedesignofouralgorithm,wehavechosenthemethodofpickingarandomshifteddissectiongivenin[3,20,21].ThereforewecanapplyalmostthesameargumentsasthoseusedbyRaoandSmith[21,Sections2.2and2.3]toderandomizeouralgorithmatsmallincreaseofthecostTheorem3.3.Foreverypositivethereexistsadeterministicalgorithmrunningin

thatforeverysetofpointsinproducestime

abiconnectedgraphspanningthepointsandhavingthecostwithinoftheminimum.Inparticular,whenandareconstant,therunningtimeis.Foraconstantandarbitrary

multigraphsuchthattheinducedgraphisasubgraphofisatmost

andtheexpectedcostof

therunningtimeis.Thealgorithm

canbeturnedintoaLasVegasonewithoutaffectingthestatedasymptotictimebounds.

RecalltheuseofSteinerpointsinthefirstattemptofderivingPTASfortheEu-clideanminimum-cost-connectivityin[5]byallowingthemsolelyontheapproxima-tionside.Asabyproduct,wecansubstantiallysubsumetheresultsonminimum-cost-connectivityfrom[5]inthecomplexityaspectbyusingTheorem4.1.

5Euclidean-edgeconnectivityingraphs

Ourspannerapproachtobiconnectivityreliesonanefficienttransformationofatwo-edgeconnectedmultigraphintoabiconnectedgraphonthesamepointsetwithoutanycostincrease.Unfortunately,itseemsthatforthereisnoanysimilarcost-efficienttransformationbetween-edgeconnectedmultigraphsand-vertex-or-edgecon-nectedgraphs.Weshowinthissectionthatanarbitrary(inparticular,minimum-cost)-edgeconnectedgraphspanningawell-roundedpointsetadmitsaseriesoftransfor-mationsresultinginan-locally-light-edgeconnectedgraphonthissetwithasmallincreaseincost.Bysomefurthersmallcostincrease,wecanmakethelattergraph

-locally-lightinordertofacilitateefficientdynamicprogramming.

Thefollowinglemmaplaysacrucialroleinouranalysis.Intuitively,itaimsatprovidingasimilartransformationoftheinputgraphasthatpresentedinLemma3.1.Themaindifficultyhereisinthefactthattheinputgraphmaybearbitrary(whileinLemma3.1wehaveanalyzedgraphshavingtheisolationproperty).

Lemma5.1.Letbeaspanninggraphofawell-roundedpointsetin.Forany

satisfyingthefollowingshifteddissectionof,canbetransformedintoagraph

threeconditions:–ifisdifferentfromthenthetotalcostofissmallerthanthatof,–foranyregionofsizeinthedissectiontherearepositivereals,,greaterthan

–if

is-edgeconnectedthensois

.

Lemma5.1guaranteesthatinthegraphresultingfromthetransformationprovidedinthelemmanoregioninthedissectioniscrossedbytoomanylongedgeshavingtheirlengthoutsidefinitenumberofintervalsoftheform,

theintervals

.Ifthereare

edgeshavingtheirlengthsoutside

and,and

–theexpected(overthechoiceoftheshifteddissection)costoftimeslargerthanthatoftheminimum-costgraph.

isatmost

-local-lightnessisaverysimplecaseofthatof-bluenessTheconceptof

usedin[6].Therefore,wecanuseasimplifiedversionofthedynamicprogrammingmethodof[6]involvingthe-connectivitycharacterizationfrom[5]inordertofindan

-locally-light-edgeconnectedgraphonawell-roundedpointsetsatisfyingtherequirementsofTheorem5.1.ThisyieldsasubstantiallyfasterPTASfortheEuclideanminimum-cost-edgeconnectivitythanthatpresentedin[6].

Theorem5.2.Letbeanarbitrarypositiveintegerandlet.Thereexistsaran-domizedalgorithmthatfindsa-edgeconnectedgraphspanningtheinputsetofpointsinandhavingexpectedcostwithinfromtheoptimum.Theexpectedrunningtimeofthealgorithmis.Inpar-ticular,when,,andareconstant,thentherunningtimeis.

6EuclideanSteinerbiconnectivity

InthissectionweprovidethefirstPTASforEuclideanminimum-costSteinerbiconnec-tivityandEuclideanminimum-costtwo-edgeconnectivity.Foranyconstantdimension

.Ourproofreliesonadecompositionofaand,ourschemerunsintime

minimum-costbiconnectedSteinergraphintominimalSteinertreesandtheuseofthesocalled-banyansintroducedbyRaoandSmith[20,21].Asabyproductofthedecomposition,wederivethefirstknownnon-trivialupperboundontheminimumnumberofSteinerpointsinanoptimalsolutiontoan-pointinstanceofEuclidean

.minimum-costSteinerbiconnectivitywhichis

Sinceforanysetofpointsintheminimum-costofabiconnectedgraphspan-ningisthesameastheminimum-costofatwo-edgeconnectedgraphspanning,intheremainingpartofthissectionweshallfocusonlyontheEuclideanminimum-costSteinerbiconnectivityproblem.Byaseriesoftechnicallemmas,weobtainthefol-lowingcharacterizationofanyoptimalgraphsolutiontotheEuclideanminimum-costSteinerbiconnectivityproblem.

Theorem6.1.Letbeaminimum-costEuclideanSteinerbiconnectedgraphspan-ningasetofpointsin.Thensatisfiesthefollowingconditions:(i)Eachvertexof(inclusiveSteinerpoints)isofdegreeeithertwoorthree.

(ii)Bysplittingeachvertexofcorrespondingtoaninputpointintodegindepen-dentendpointsoftheedges,graphcanbedecomposedintoanumberofminimalSteinertrees.hasatmostSteinerpoints.(iii)

6.1PTAS

Ourspanner-basedmethodforEuclideanminimum-costbiconnectivitycannotbeex-tendeddirectlytoincludeEuclideanminimum-costSteinerbiconnectivitysincespan-nersdonotincludeSteinerpoints.Nevertheless,thedecompositionofanoptimalSteinersolutionintominimumSteinertreesgiveninTheorem6.1opensthepossibilityofusingtheaforementionedbanyanstoallowSteinerpointsforthepurposeofapproximatingtheEuclideanminimumSteinertreeproblemin[20].

-banyanofasetofpointsinisageometricalDefinition6.1.[20]A

graphonasupersetof(i.e.,Steinerpointsareallowed)suchthatforanysubsetof,thecostoftheshortestconnectedsubgraphofthebanyanwhichincludes,isat

timeslargerthantheminimumSteinertreeof.most

RaoandSmithhaveprovedthefollowingusefulresultonbanyansin[20].Lemma6.1.Let.Onecanconstructa-banyanofan-pointsetin

whichusesonlySteinerpointsandhascostwithinafactorof

oftheminimumSteinertreeoftheset.Therunningtimeoftheconstruc-tionis.

Bycombiningthedefinitionofwegetthefollowinglemma.

-banyanwithTheorem6.1(2)andLemma6.1,

letbea-banyanconstructedLemma6.2.Forafinitepointsetin

accordingtoLemma6.1.Letbethemultigraphobtainedfrombydoublingitsedges.Thereisatwo-edgeconnectedsub-multigraphofwhichincludesandwhosecostiswithinoftheminimumcostoftwo-edgeconnectedmultigraphonanysupersetof.

Letbethemultigraphresultingfromscalingandperturbingallthevertices(i.e.,

specifiedinLemma6.2accordingtothealsotheSteinerpoints)ofthemultigraph

firststepinSection3.Theverticesofareonaunitgridand,byarguinganalogouslyasinSection3,aminimum-costtwo-edgeconnectedsub-multigraphof

thatincludesiswithinofaminimum-costtwo-edgeconnectedsub-thatincludes.multigraphof

Thepatchingmethodof[5]appliedtoyieldsthefollowingstructuretheorem.

Theorem6.2.Chooseashifteddissectionofthesetofverticesofthebanyanat

random.Thencanbemodifiedtoamultigraphsuchthat:–is-lightwithrespecttotheshifteddissection,where

4.D.Bienstock,E.F.Brickell,andC.L.Monma.Onthestructureofminimum-weight-connectedspanningnetworks.SIAMJ.Disc.Math.,3(3):320–329,1990.

5.A.CzumajandA.Lingas.ApolynomialtimeapproximationschemeforEuclideanminimumcost-connectivity.Proc.25thICALP,pp.682–694,1998.

6.A.CzumajandA.Lingas.Onapproximabilityoftheminimum-cost-connectedspanningsubgraphproblem.Proc.10thACM-SIAMSODA,pp.281–290,1999.7.G.N.FredericksonandJ.J´aJ´a.OntherelationshipbetweenthebiconnectivityaugmentationandTravelingSalesmanProblem.Theoret.Comput.Sci.,19(2):1–201,1982.

8.M.R.GareyandD.S.Johnson.ComputersandIntractability:AGuidetotheTheoryof

-completeness.Freeman,NewYork,NY,1979.

9.M.Gr¨otschel,C.L.Monma,andM.Stoer.Computationalresultswithacuttingplanealgo-rithmfordesigningcommunicationnetworkswithlow-connectivityconstraints.OperationsResearch,40(2):309–330,1992.10.M.Gr¨otschel,C.L.Monma,andM.Stoer.Designofsurvivablenetworks.Handbooksin

OperationsResearchandManagementScience,volume7:NetworkModels,ch.10,pp.617–672.North-Holland,Amsterdam,1995.

11.E.N.GilbertandH.O.Pollak.Steinerminimaltrees.SIAMJ.Appl.Math.,16(1):1–29,

1968.

12.M.X.GoemansandD.P.Williamson.Theprimal-dualmethodforapproximationalgorithms

anditsapplicationtonetworkdesignproblems.Chapter4in[15],pp.144–191.

13.J.Gudmundsson,C.Levcopoulos,andG.Narasimhan.Improvedgreedyalgorithmsforcon-structingsparsegeometricspanners.ToappearinProc.7thSWAT,2000.

14.D.F.HsuandX-D.Hu.Onshorttwo-connectedSteinernetworkswithEuclideandistance.

Networks,32(2):133–140,1998.

15.D.S.Hochbaum,editor.ApproximationAlgorithmsfor-HardProblems.PWSPublish-ingCompany,Boston,MA,1996.

16.F.K.Hwang,D.S.Richards,andP.Winter.TheSteinerTreeProblem.North-Holland,Am-sterdam,1992.

17.S.Khuller.Approximationalgorithmsforfindinghighlyconnectedsubgraphs.Chapter6in

[15],pp.236–265.

18.D.Krznaric,C.Levcopoulos,G.Narasimhan,B.J.Nilsson,andM.Smid.Theminimum

2-connectedsubgraphofasetofpoints.Manuscript,September15,1997.

19.J.S.B.Mitchell.Guillotinesubdivisionsapproximatepolygonalsubdivisions:Asimple

polynomial-timeapproximationschemeforgeometricTSP,-MST,andrelatedproblems.SIAMJ.Comput.,28(4):1298–1309,1999.

20.S.B.RaoandW.D.Smith.Approximatinggeometricalgraphsvia“spanners”and

“banyans.”Proc.30thACMSTOC,pp.540–550,1998.Afullversionappearedin[21].21.S.B.RaoandW.D.Smith.Improvedapproximationschemesforgeometricalgraphsvia

“spanners”and“banyans.”May1998.Anextendedabstractappearedin[20].

22.M.Stoer.DesignofSurvivableNetworks,volume1531ofLectureNotesinMathematics.

Springer-Verlag,Berlin,1992.

23.K.Steiglitz,P.Weiner,andD.J.Kleitman.Thedesignofminimumcostsurvivablenetworks.

IEEETrans.CircuitTheor.,16:455–460,1969.