AlgorithmsFransSchalekampCornellIthaca,forUniNYvtheersityUniversalandCornellDavidIthaca,B.UniShmoANYversityPrioriys TSP ∗ univWersalepresentTSP,wetwoshosimpleresultswthatoneforcangeneralizationscomputeAbstractatourofthatthetraisvunielingversallyoptimalwhenesalesmanproblem(TSP):vertheForinputthe iscorollaryatree.metric.A(randomized)O(log n)-approximationalgorithmfortheaprioriTSPfollowsasa Keywords:TravelingSalesmanProblem,APrioriOptimization,UniversalOptimization,MetricEmbedding ∗ RhodesCorrespondingHall,Ithaca,authorNY14853..Emailaddress:fms9@cornell.edu.Postaladdress:SchoolofORIE,CornellUniversity,288 1 1 ConsiderIntroduction setis xedtheandfolloknowingwn,bproblem:uteachdayAdelionlyveryasubsetpersonneedsofthepotentialclienttoserveclientsseteachneedsdayto.Herbeserv(potential)cliented.Insteadof reoptimizingeveryday,thedeliverypersonwouldliketohaveatourofthepotentialclientset,suchthat ifshetravelsthesubtourinducedfromthecompletetourforthatday'ssubsetofclients(i.e.,shevisitsthe clientsinthesameorderasthecompletetour,shortcuttingthetourwhereclientsareabsent),thenshedoes nottraMorepreciselyvelmuchmore,twthanodifhadferentproblemssheusedthecanoptimalbeconsidered.tourforthisOneparticularsubsetisanadversialofmodel,whereclients. anyofthe subsetsclientsispossible,andtheobjectiveistominimizethemaximumratio,overallpossibleclient subsets,ofthelengthoftheinducedsubtourtothelengthoftheoptimaltourforthatsubset.(Anotherway toviewthisisthattheoptimizerannouncesthecompletetour,andnexttheadversarycandecidewhich subsetofclientsactuallyneedservice).Thisisknownastheuniversaltravelingsalesmanproblem. subsetsAsecondmodelofclientsandistheaprobjectiobabilisticveismodel.tominimizeHeretheoneassumesexpectedlengththatthereoftheissomeprobabilitydistribinducedsubtour.Thisproblemutionon isknownastheaprioritravelingsalesmanproblem.(Notethattherearecomplexityissuesarisingfrom specifyingtheprobabilitydistribution.) solvIneboththisproblemsoptimallypaperwewillshow,thatandwhenwecantheevclientdistancesensolvetheprobabilisticmodelwithoutformatreemetric,wecan,anyquiteknowledgesurprisinglyofthe, probabilitydistribution.Thisspecialcaseoftreemetricsisparticularlysigni cant,becauseanymetriccanbe(probabilistically) embeddedintreemetricswithexpecteddistortionO(log n) (whereisthenumberofpointsinthemetric), asshownbyFakcharoenphol,RaoandTalwar[10](buildingonBartal'swork[1]).Asacorollarywe O(log n) thereforegetthattheaprioriTSPonanymetricspacecanbesolvedwithin ofoptimal,even withoutanyknowledgeofthedistributionon subsets.Itisinterestingtonotethatthisisthesame guaranteeTheuniasversalPlatzmanTSPandwasBartholdi'motivatedsresultbygettingforthegoodunivsolutionsersalTSPforproblemn thefMealsintheEuclideanplaneOnWheelsfprogram[2,17].of SeniorCitizenServicesInc.,fwhichdeliverspreparedlunchestopeoplewhoareunabletoshoporcookfor themselvesf[3].Thelistofclientsthatneedservicein2thisparticularapplicationisquitevolatilef...because ofthenatureoftheclients:mostareelderlyorill.Theymaydie,orrecoverfromillness,orreceive careelsewhere...f[3].Theapproximationalgorithmof[2,17]usesaspace llingcurvetomappointsfrom theplanetotheunitline(interpretedasacircle),onwhichatravelingsalesmantouristrivialtosolve. O(log n) O(1) Theyprovedaperformanceguaranteeof ,andconjecturedthatitwasreally .Bertsimas andGrigni[5]disprovedthisconjectureforBartholdiandPlatzman'salgorithm,exhibitinga(familyof) counterexample(s)RecentlytheuniforversalwhichTSPO(loghasnag) isaintightbecomeuptoanamultiplicatiobjectofvstudyeconstant.,with[15]givinganalgorithmfor O(log4 n/ log log n) whichrecentlythe[11]inducedimprovtouresthisforboundanysubsettoiswithin,usingantheideasof[10].Alofactorwerboundofoptimal,fortheand2-dimensionalevenmore O(log2 n) EuclideanuniversalTSP(i.e.,independentofanalgorithm)of waspresentedin[12].Ω( 6 log n/ log log n) asymptoticresultsJailletintroducedonthepointsdistribnotionofautedprioriindependentlyoptimization,andinparticularuniformlytheonaprioriplaneTSP[14,[13,6,4],14].notExceptmuchforis known.(Note,ofcourse,thatanyguaranteefortheuniversalTSPimpliesthesameguaranteefortheapriori TSP.) √ solutionIn[8]suchandthat[7]atherelatedquestioninducedsubtourswasarestudied,namelyactuallyoptimalsolutions,forwhatmetricstothedoessmallerproblems?thereexistauniOrversalphrasedTSP differently,whatmetricsgiveauniversalTSPsolutionwithoptimalratioequalto1?Thispropertyiscalled themastertourpropertyanditturnsoutthattheclassofmetricsthatpossessthispropertyisfullydescribed andknownasKalmansonmetrics,asshownin[8]. 2APrioriandUniversalTSP Westartbyintroducingsomenotationneededtopresentourresults.Forthetravelingsalesmanproblem,theinputconsistsofa nitesetofpointsV andafdistanceffunctiond : V × V ;= {1, 2,...,n}→ Q≥0 τ Vd(τ)= wewishto ndatour,givenbyapermutationofallpointsin,suchthatthelengthofthetour, Σ n−1 d(τi,τi+1)+ d(τn,τ1) i=1 Fortheapriorianduniversalisminimized.TSP,onlyasubsetS ⊆ V willbefactivef.Foratourof,wede ne τV τ(S) S (τ (S))i = τj τj ∈ S #{τk ∈ S, k ≤ j} = i (whereto # be{N the} tourdenotesrestrictedthecardinalityto,i.e.oftheset).where3Forjeachissuchthat,wealsoandletOP T (S) denotetheNS ⊆ V optimaltouronandletd(OP T (S)) denoteitslength. . VdwantTheatourinput.andTheoutputobjectiforve,thehoweuniverver,nosalwTSPistoareminimize,thesameovaserforallsubsetstheTSP:S we ⊆ V are,thegivratioenofandthelength,andweofthetourinducedbythepermutationτ on,dividedbythelengthoftheoptimaltouron,i.e.tominimizemaxS⊆V [d(τ (S))/d(OP T (S))] probabilitydistribFortheapriori S utionTSPspeci ed,theinputoviseragtheainsubsetsasetofofpoints.(For,andouraresults,distancefunctionitturnsoutdthat,butwetheredonotisalsoneeda . Vτanyknowledge τ ofthisdistribution.)Thegoalnowisto ndatourthatminimizestheexpectedlength(withrespecttotheprobabilitydistribution S onsubsetsof)ofthetourinducedby S ;i.e.,tominimizeES [d(τ|S)]Letbea nitesetofpoints.Adistancefunctiond : VV × V → Q≥0 iscalledametricif(1) Vd(i, i)=0 forall and(2) forall (thetriangleinequality).(Tobeprecise, i ∈ Vd(i, j) ≤ d(i, k)+ d(k, j) i, j, k ∈ V thisisthede nitionofasemimetric.Forasemimetricto Vbeametricwealsowant τ if , d(i, j) > 0 i 6= j butthisisofnowithimportancenodesV for T thisandpaperlengthsassociated.)Furthermore,wewithsaythethatedges,isasuchtreethatmetricifthereisexactlyequalexistsatree T =(VT ,ET ) ⊇ Vd(i, j) T ij i,j ∈ V tothelengthoftheuniquepathinfromto,forall .ForeachsubsetS ⊆ V ,onecanobtainan inducedtree ,whichistheunionoverallpairsofnodesi, j ∈ S oftheedges(andnodes)inthepath T (S) betweeni and.Wecannowstateandproveourresults. d Lemma1ConsideraninputtotheTSPgivenbyatreemetriconthatisrealizedbythetree;thenfor anysubsetS ⊆ V ,thelengthofanytouronisatleasttwicethetotallengthoftheedgesintheinducedtree . j T (S) Proof.Takeanytravelingsalesmantouron.Wecantransformthistoawalkusingtheedgesof , τS T (S) thisbyinserting,betweendoesnotchangetheeachlengthpairofoftheconsecutitour.Sove S wepointscanviei andwanyintour,the V asauniquewalkthatpathonlyinTusesconnectingtheedges Ti andof; treeT (S) (multipletimes).However,consideranyedgein ;ifwedeletethisedge,thenweseparate T (S) thetree intotwocomponents,therebypartitioningS intotwonon-emptysubsetsS1 and.Thus,the T (S) S2 walkmustcontainthisedgeatleasttwiceinthetour,atleastj oncefenteringfτS1 andatleastoncefleavingfj 4 it.Foranytree,wecanconsiderthewalkformedbytraversingfaroundtheoutsidefof:weshallcall thissuchwtoursalktrareavthe.samelength,SuchawalkandcanbybeLemmashortcut1inareanumberalloptimalsolutionsofwaystoobtaintotheatour;TSP.forItisaeasytreetometric,seethatall ifwestartwithonesuchtour,andconsiderthetour foranysubset ,thenthistourcanbe ττ(S) S ⊆ V obtainedbyshortcuttingT thewalktrav .Henceτ(S) isanoptimalsolutiontotheTSPT inputinduced (T (S)) by,andweha(T v ) eshownthefollowingresult. S Theorem2Foranytreemetric,anyshortcuttingofthewalktrav(T ) yieldsanoptimalsolutiontothe universalTSP,andthereforeanoptimalsolutionto aprioriTSP. metrics,NoteandthatthethefactresultsthatKalmansonmetricsabovearealsoimpliedhavebythethemasterfactthattourtreepropertymetricsasproarevedasubclassin[8].TheofKalmansonproofshere aremuchsimpler,aswejustconsidertreemetrics. Corollary3Thereisapolynomial-timerandomizedalgorithmthat,foranymetricinputtotheTSP τS ⊆ Vτ (S) onn points,computesatoursuchthatforeachsubset ,theexpectedcostofthetour is O(log n)d(OP T (S)) (wheretheexpectationiswithrespecttotherandomchoicesofthealgorithm). Proof.Use(Bartal's)stochastictreeembedding[1,9,10]:thisgivesadistributionovertreemetrics,, suchthat forall ,and forall d .(We dT (i, j) ≥ d(i, j) i, j ∈ VET [dT (i, j)] = O(log(n))d(i, j) i, j ∈ V ET willuseandtoeachdenoteinthetheexpectationdistribution,withnoterespectthattothistravdistributionoverthetreemetrics.),sinceForeachsubsetisthe S ⊆ VT dT ((T (S)) ≤ dT (OP T (S)) OP T (S) optimaltourforwithrespecttotheoriginaldistancemetric,whereasthetraversalyieldstheoptimaldT Sd dT ET [dT ((T (S)))] ≤ ET [dT (OP T (S))] tourfor.Therefore, trav S ⊆ V foreach .Wecannowconcludethat ET [d((T (S)))] ≤ ET [dT ((T (S)))] ≤ ET [dT (OP T (S))] = O(log n)d(OP T (S)), trav trav wherethe rstandthirdinequalitiesareduetheproperties5 oftheembedding(non-shrinking,andinexpec tationexpandingbyatmostO(log n)). Corspaceollarywith4n pointsThereisŠaevenrandomizedwithoutspecifyingO(log n)-approximationalgorithmtheprobabilitydistributionforontheasubsets.prioriTSPonanymetric Proof.TheresultfollowsratherdirectlyfromCorollary3.Denoteby theprobabilitythatsubset foccursf.olvanThexpectationxpectedcostrespect(with thetotheofrandomistreemetric)ofouraprioriTSPsolution(which invesee with respecttochoice)S ΣΣ trav trav pS S ET [ pS d((T (S)))] = pS ET [d((T (S)))] = pS O(log n)d(OP T (S)) S = O(log n) pSd(OP T (S)) S = O(log n)ES [d(OP T (S))]. IfAP OP Tand(S) denotesthe S optimalaprioritourrestricted ΣS ,to,isxactlyd(OP T (optimalS)) ≤ dalue(AP OP Tthe(S))priorifor each,so whichthenethevforaSES (d(OP T (S))) ≤ ES (d(AP OP T (S))) TSPNote. however,thatthisdoesnotimplyaO(log n) boundfor Σ theuniversalTSPproblem.Theuniversal maxS d((T (S))/d(OP T (S)) TSPquantitybasedis withthearaaboe.Itis, S wecannotconcludethatwecanan thisconcernedongumentstrvvinterestingandtonote obtainanalogousresultsythingdirectlyabout forBertsimasvariants[4].oftheapriorianduniversalminimumspanningtreeandSteinertreeproblemsasintroducedby aprioriFinallyTSP,noteusingthatthethetechniqueresultinof[16]probabilisticallyembeddingimpliesthatitisnotpossiblethemetricto ndinacutbetterapproximationmetrics(acutmetricforisthea Σ metricd thatcanberepresentedas ),ofwhichtreemetricsareasubclass.d(i, j)= S:|{i,j}∩S|=1 wS 6 Acknowledgments Wtheemasterwouldtourliketopropertythank.theanonymousrefereeforpointingouttheconnectiontoKalmansonmetricsand portedpartiallyResearchofbytheNSF rstgrantsCCR-0430682authorsupportedpartially&DMI-0500263.byNSFgrantCCR-0430682,ofthesecondauthorsup-References. ofof algorithmicapplications.1996) 37th [1]YAnnualSymposiumBartal.ProbabilisticapproximationonFoundationsComputerScience(Burlington,metricspacesanditsVT, ,pages184OE193.IEEEIn [2]Comput.J.space llingcurvJ. Soc.Press,IIIes.andOperLosL..Alamitos,K.Res.Platzman.Lett.CA,,1(4):121OE125,1981/82.An1996. O(N log N) planartravellingsalesmanheuristicbasedon [3]systemJ.J.Bartholdi,formealsIII,onL.wheels.K.Platzman,InterfacesR.L.,Collins,13(3):1OE8,1984.andW.H.Warden,III.Aminimaltechnologyrouting [4]D.Mass.,1988.Bertsimas.ProbabilisticCombinatorialOptimizationProblems.PhDthesis,MIT,Cambridge, [5]traD.vBertsimaselingsalesmanproblem.andM.Grigni.OperWorst-caseationsResearexampleschforLetterthes,space llingcurv8(5):241OE244,October1989.eheuristicfortheeuclidean [6]D.1033,1990.J.Bertsimas,P.Jaillet,andA.R.Odoni.Apriorioptimization.OperationsResearch,38(6):1019OE [7]G.Christopher,M.Farach,andM.Trick.Thestructureofcirculardecomposablemetrics.In AlgorithmsŠESA,Berlin,1996.'96(Barcelona),volume1136ofLectureNotesinComput.Sci.,pages486OE500. [8]SpringerSIAMV.G.DeJ. nekDiscro,eteR.Math.Rudolf,,11(1):81OE93,1998.andG.J.Woeginger.Sometimestravellingiseasy:themastertourproblem. 7 [9]J.metrics.448OE455(electronic),F InProceedingsS.NeRao,wofYtheandork,Thirty-FK.2003.TalwAiftharCM..AnnualAtightboundACMSymposiumon onTheoryofComputingmetrics,bypagestree [10]metrics.J.Fakcharoenphol,J.Comput.SystemS.Rao,Sci.and,K.69(3):485OE497,2004.Talwar.Atightboundonapproximatingarbitrarymetricsbytree [11]A.USA,2006.theGupta,seventeenthannualM.ATCM.Hajiaghayi,Press.ACM-SIAMsymposiumandH.Rack¨e.OblionviousnetwDiscretealgorithmorkdesign.,pages970OE979,InSODA'06:NeProceedingswYork,NYof, [12]M.inplanarmetrics.T.Hajiaghayi,R.InKleinberSODA'06:g,andProceedingsT.Leighton.ImprooftheSeventeenthAnnualvedlowerandupperboundsACM-SIAMSymposiumforuniversaltspon [13]DiscrP.Jaillet.ProbabilisticeteAlgorithms,pages649OE658,travelingsalesmanproblems.NewYork,NY,USA,2006.TechnicalReportACMPress.185,OperationsResearch [14]CenterareP.Jaillet.visited.,MITAOperpriorisolution,1985.ationsResearofactrah,v36:929OE936,1988.elingsalesmanprobleminwhicharandomsubsetofthecustomers [15]tree,L.Jia,andG.Lin,setcoG.verNoubir.In,STR.OCRajaraman,'05:ProceedingsandR.Sundaram.oftheThirty-seventhAnnualUniversalapproximationsACMforSymposiumTSP,Steineron [16]TTheory.LeightonofComputingandS.Rao.,pages386OE395,Multicommoditymax- oNewYork,NYw,USA,2005.min-cuttheoremsACMPress.andtheiruseindesigning approximationalgorithms.J.ACM,46(6):787OE832,1999. [17]JL..AK.CMPlatzman,36(4):719OE737,1989.andI.JohnJ.Bartholdi.Space llingcurvesandtheplanartravellingsalesmanproblem. 8