THEORY OF COMPUTING,Volume2(2006),pp. 53–64 http://theoryofcomputing.org An Improved Approximation Ratio for the ∗ Covering Steiner Problem Anupam Gupta† Aravind Srinivasan‡ Received: August4,2005;published: February17,2006. Abstract: IntheCoveringSteiner problem,wearegivenanundirectedgraphwithedge- costs, and some subsets of vertices called groups, with each group being equipped with a non-negativeintegervalue(calleditsrequirement);theproblemistofindaminimum-cost treewhichspansatleasttherequirednumber ofverticesfromeverygroup. TheCovering Steinerproblemisacommongeneralizationofthek-MSTandtheGroupSteinerproblems; indeed, whenalltheverticesofthegraphlieinonegroupwitharequirementofk, weget thek-MSTproblem,andwhentherearemultiplegroupswithunitrequirements,weobtain theGroupSteinerproblem. Whilemanycoveringproblems(e.g.,thecoveringintegerprogramssuchassetcover) become easier to approximate as the requirements increase, the Covering Steiner problem ∗A preliminary version of this work appears in the Proc. Foundations of Software Technology & Theoretical Computer Science, 2003. PartofthisworkwasdonewhiletheauthorswereatLucentBellLaboratories, 600-700MountainAvenue, MurrayHill,NJ07974-0636,USA. †TheresearchofthisauthorwassupportedinpartbyaNationalScienceFoundationCAREERawardCCF-0448095,and byanAlfredP.SloanFellowship. ‡TheresearchofthisauthorwassupportedinpartbytheNationalScienceFoundationunderGrantNo.0208005andITR AwardCNS-0426683. ACMClassification: C.2.0,F.2.2,G.1.6,G.3 AMSClassification: 68W20,68W25,90C59 Key words and phrases: Algorithms, Approximation Algorithms, Steiner Trees, Randomized Algo- rithms,NetworkDesign AuthorsretaincopyrighttotheirworkandgrantTheoryofComputingunlimitedrights topublishtheworkelectronicallyandinhardcopy. Useoftheworkispermittedas longastheauthor(s)andthejournalareproperlyacknowledged. Forthedetailed copyrightstatement,seehttp://theoryofcomputing.org/copyright.html. (cid:13)c 2006AnupamGuptaandAravindSrinivasan DOI:10.4086/toc.2006.v002a003 A.GUPTAANDA.SRINIVASAN remains at least as hard to approximate as the Group Steiner problem; in fact, the best guarantees previously known for the Covering Steiner problem were worse than those for Group Steiner as the requirements became large. In this work, we present an improved approximation algorithm whose guarantee equals the best known guarantee for the Group Steinerproblem. 1 Introduction We present an improved approximation algorithm for the Covering Steiner problem. This problem has the following property that goes against the norm for covering problems: its approximability cannot get better as the covering requirements increase. Thus the approximation ratio of the general Covering Steiner problem is at least as large as for the case of all unit requirements, which is just the Group Steiner problem. In this work, we improve on the known approximation algorithms for the Covering SteinerproblemgivenbyEvenetal.[3]andKonjevodetal.[11]. Ourresultsmatchtheapproximation guarantee of the known randomized algorithm for the Group Steiner problem due to Garg et al. [6] (seethepaperofCharikaretal.[2]foradeterministicalgorithm). Asuitablemeldingofarandomized roundingapproachwithadeterministic“thresholdrounding”methodleadstoourresult. LetG=(V,E)beanundirectedgraphwithanon-negativecostfunctioncdefinedonitsedges. Let a family G={g ,g ,...,g } of k subsets ofV be given; we refer to these sets g ,g ,...,g as groups. 1 2 k 1 2 k For each group g, a non-negative integer r ≤|g| is also given, called the requirement of the group. i i i TheCoveringSteinerproblemonGistofindaminimum-costtreeinGthatcontainsatleastr vertices i fromeachgroupg;thespecialcaseofunitrequirements(i.e.,r =1foralli)correspondstotheGroup i i Steinerproblem. WedenotethenumberofverticesinGbyn,thesizeofthelargestgroupbyN,andthe largest requirement of a group by K. Logarithms in this paper will be to the base two unless specified otherwise. As in the paper of Garg et al. [6], we focus on the case where the given graph G = (V,E) is a tree, since the notion of probabilistic tree embeddings [1] can be used to reduce an arbitrary instance of the problem to a instance on a tree. Specifically, via the result of Fakcharoenphol et al. [4], a ρ– approximationalgorithmontree-instancesimpliesanO(ρlogn)–approximationalgorithmforarbitrary instances. In fact, we can assume that the instance is a rooted tree instance where the root vertex must beincludedinthetreethatweoutput;thisassumptioncanbedischargedbyrunningthealgorithmover allchoicesoftherootandpickingthebesttree. Given an instance of the Covering Steiner tree problem, one can get an O(k) approximation algo- rithmusingwell-knownideaswithoutresortingtothereductiontotreeinstancesoutlinedabove. Indeed, onecanusethe2-approximationalgorithm(givenbyGarg[5])fortherootedr-MSToneachgroupg i i separately, and return the union of the k trees obtained. However, in case the number of groups k is large, one may prefer an algorithm whose dependence on the number of groups k is better than linear, perhaps at the expense of additional logarithmic terms. And indeed, such results are possible: for the special case of the Group Steiner tree problem (where K =1), the current-best approximation bound for tree instances is O(logk·logN). For the Covering Steiner problem, the current-best approximation THEORYOFCOMPUTING,Volume2(2006),pp. 53–64 54 ANIMPROVEDAPPROXIMATIONRATIOFORTHECOVERINGSTEINERPROBLEM algorithmfortreeinstancesisO((logk+logK)·logN)[3,11];also,anapproximationboundof (cid:18) logN·log2k (cid:19) O log(2(logN)·(logk)/logK) isalsopresentedin[11],whichisbetterifK≥2a(logk)2 wherea>0isaconstant. Asmentionedabove, weneedtomultiplyeachofthesethreeapproximationboundsbyO(logn)toobtainthecorresponding resultsforgeneralgraphs. Notethattheaboveapproximationratiosgetworseastherequirementsincrease,i.e.,asK increases. This is unusual for covering problems, where the approximability usually gets better as the coverage requirementsincrease. Thisiswell-known,forinstance,inthecaseofcoveringintegerprogramswhich include the set cover problem; the “multiple coverage” version of set cover is one where each element ofthegroundsetneedstobecoveredbyatleastagivennumberofsets. Inparticular,theapproximation ratioimprovesfromlogarithmictoO(1)(oreven1+o(1))forfamiliesofsuchproblemswherethemin- imumcoveringrequirementBgrowsasW (logm),whenmisthenumberofconstraints(see,e.g.,[12]). Inlightoftheseresults,itisnaturaltoaskwhethertheapproximationguaranteefortheCoveringSteiner problemcanbebetterthanthatfortheGroupSteinerproblem. This question can easily be answered in the negative; indeed, given a rooted tree instance of the Group Steiner problem and an integer K, we can create an instance of the Covering Steiner problem as follows: increase the requirement of every group from 1 to K, connect K−1 dummy leaves to the rootwithedge-costzeroandaddtheseleavestoallthegroups. Itiseasilyseenthatanysolutiontothis Covering Steiner instance can be transformed to a solution to the original Group Steiner instance with nolargercost,andthatthetwoinstanceshavethesameoptimalsolutionvalue. Therefore,theCovering SteinerproblemisatleastashardtoapproximateastheGroupSteinerproblem. (Thisfactwaspointed outtousbyRobertKrauthgamer.) We are thus led to the question: can the Covering Steiner problem be approximated as well as the GroupSteinerproblem? Thefollowingtheoremanswersthisquestionintheaffirmative: Theorem1.1. Thereisarandomizedpolynomial-timeapproximationalgorithmforthecoveringSteiner problem which, with high probability, produces an feasible solution with an approximation ratio of (i) O(logN·logk)fortreeinstances,and(ii)O(logn·logN·logk)forgeneralinstances. This implies an improvement of Q ((logn)/loglogn) over previous results in some situations; in- deed, thisisachievedwhen, say, k=log2+Q (1)nandK =nQ (1). (Thereasonwetakek(cid:29)log2ninthis example is that the problem on trees is approximable to within O(k) as noted earlier, and so if k was small,wewouldhaveagoodapproximationalgorithmanyway.) The bounds for tree instances are essentially the best possible in the following asymptotic sense: the paper of Halperin and Krauthgamer [8] shows that, for any constant ε >0, an O((log(n+k))2−ε)- approximationalgorithmfortheCoveringSteinerproblemimpliesthatNP⊂ZTIME[exp{(logn)O(1)}]. (Technically, the hardness is shown for the rooted version of the problem, but this is without loss of generality, sincethe rooted versioncan bereduced tothe unrootedversion by introducinga newgroup g containingonlytherootvertexrandhavingunitrequirement.) Furthermore,sinceweadoptanatural 0 linear programming (LP) relaxation considered by Garg et al. [6] and Konjevod et al. [11], we would like to note that the integrality gap of this relaxation for tree-instances of Group Steiner is W (logk· THEORYOFCOMPUTING,Volume2(2006),pp. 53–64 55 A.GUPTAANDA.SRINIVASAN logN/loglogN) [7]. Since this integrality gap naturally extends to the Covering Steiner problem as well,thissuggeststhatourtechniquescannotimprovetheapproximationguaranteesubstantially. 1.1 OurTechniques Our approach to solving the Covering Steiner problem is to iteratively round an LP relaxation of the problem suggested by Konjevod et al. [11]. Given a partial solution to the problem, we consider the fractionalsolutionoftheLPforthecurrentresidualproblem,andextendthepartialsolutionusingeither arandomizedroundingapproachoradirectdeterministicapproach. Informally,inordertodobetterthantheapproachofKonjevodetal.[11],themaintechnicalissuewe handleisasfollows. LetOPTdenotetheoptimalsolutionvalueofagiventreeinstance. Inessence,each iterationof[11]addsanexpectedcostofO(OPT·logN)tothesolutionconstructedsofar,andreduces thetotalrequirementbyaconstantfraction(inexpectation). Sincetheinitialtotalrequirementisatmost k·K, we thus expect to run for O(logk+logK) iterations, resulting in a total cost of O(OPT·(logk+ logK)logN)withhighprobability. ToeliminatethelogK termfromtheirapproximationguarantee,we show,roughly,thateveryiterationhastosatisfyoneoftwocases: either(i)agoodfractionofthegroups have their requirement cut by a constant factor via a threshold rounding scheme, while paying only a costofO(OPT),or(ii)arandomizedroundingschemeisexpectedtofullycoveraconstantfractionof thegroups. AchipgamepresentedinSection3isusedtoboundthenumberofiterationswherecase(i) holds;Janson’sinequality[9]andsomedeterministicargumentsareusedforcase(ii). Intheinterestof thecleanestexposition,wehavenotattemptedtooptimizeourconstants. 2 Preliminaries The analysis of our algorithm will use an inequality due to Janson [9], which we now state. Let W be a set of elements, and let us pick a random set R by picking each e∈W independently with some probability p . Let {A ⊆W | j ∈J} be some family of subsets of W , and we say that j ∼ j0 if j 6= j0 e j andA ∩A 6=0/. DefineB tobetheeventthatA ⊆R,andletD =(cid:229) Pr[B ∩B ]. IfY isthe j j0 j j j<j0:j∼j0 j j0 j indicatorvariableforeventB ,letµ =E[Y ]=Pr[B ],andµ =(cid:229) µ. ThenJanson’sinequalitysays j j j j j∈J i that Theorem2.1. Foranyδ ∈[0,1], (cid:2)(cid:229) (cid:3) (cid:26) δ2µ (cid:27) Pr Y ≤(1−δ)µ ≤exp − . (2.1) j 2+(D /µ) j 3 A Chip Game Consider the following chip game. We initially have chips arranged in k groups, with each group g i (init) having some number n ≤K of chips. Chips are iteratively removed from the groups in a manner i describedbelow; agroupiscalledactiveifthenumberofchipsinitisnonzero. Thegameproceedsin rounds: ineachround,wechooseroughlyhalfofthecurrentlyactivegroupsandhalvetheirsizes,until therearenomoreactivegroupsleft. Formally,thegameisasfollows: THEORYOFCOMPUTING,Volume2(2006),pp. 53–64 56 ANIMPROVEDAPPROXIMATIONRATIOFORTHECOVERINGSTEINERPROBLEM 1. Atthestartofsomeround,letn denotethenumberofchipsingroupg. LetAdenotethenumber i i ofgroupscurrentlyactive;i.e.,A=|{i|n 6=0}|. i 2. WechooseanysetofatleastdA/2eactivegroups. 3. For each of these chosen groups g, we remove at least dn/2e chips, causing the new number i i of chips in group g to become at most bn/2c. Note that this may cause some of the groups to i i becomeinactive. 4. Iftherearenomorechipsleft,westop,elsewegobacktoStep1. Intheanalysisbelow,itwillnotmatterthattwoconstantsinSteps2and3abovewere1/2each;any twoconstantsa,b∈(0,1)leadtothesameasymptoticresultinthefollowinglemma. Lemma3.1. ThemaximumnumberofroundspossibleintheabovechipgameisO(logk·logK). Proof. To bound the number of rounds, we proceed as follows. We now modify the game into an (init) equivalent format. We initially start with 1+blogn c chips in each group g; once again, a group i i is active if and only if its number of chips is nonzero. Now, in any round, we choose at least half of the currently-active groups, and remove at least one chip from each of them. Note that this simple “logarithmic transformation” does not cause the maximum number of rounds to decrease, and hence we can analyze the game on this transformed instance. Let N be the number of rounds in which at 1 least k/2 groups are active. In each of these rounds, at least k/4 chips get removed. However, since thetotalnumberofchipsisatmostk(1+logK),thenumberofsuchroundsN isatmost4(1+logK). 1 Proceedinginthismanner,weseethatthetotalnumberofroundsisO(logk·logK),asclaimed. TheproofaboveindicateshowtoprovethattheboundprovedaboveinLemma3.1istight,andthere are runs of the chip game which require Q (logk·logK) rounds. Suppose all the groups start off with exactlyKchips. Wefirstrepeatedlykeepchoosingthesamesetofdk/2egroupsforremovingchips,and do this until all these groups become inactive; we need Q (logK) rounds for this. We are now left with about k/2 active groups. Once again, we repeatedly keep removing chips from the same set of about k/4activegroups,untilallofthesebecomeinactive. Proceedinginthismanner,wecangoforatotalof Q (logk·logK)rounds. 4 The Algorithm and Analysis Inthissection,wepresentouralgorithmfortheCoveringSteinerproblem,andanalyseit. Asmentioned in the introduction, we will assume that the input consists of a rooted tree T, where the root r must be included in the output solution. Furthermore, we assume (without loss of generality) that every vertex belongingtoagroupisaleafofT,andthateveryleafbelongstosomegroup. 4.1 TheBasicApproach As in previous papers on the Covering Steiner and Group Steiner problems, the broad idea of the al- gorithm is to proceed in iterations; each iteration produces a subtree rooted at r that provides some THEORYOFCOMPUTING,Volume2(2006),pp. 53–64 57 A.GUPTAANDA.SRINIVASAN additionalcoveragenotprovidedbythepreviousiterations. Thisprocessiscontinueduntiltherequired coverageisaccomplished,andtheunionofallthetreesconstructedisreturnedasoutput. Consider a generic iteration; we will use the following notation. Let r0 denote the residual require- i mentofgroupg;callthegroupg activeifandonlyifthisresidualrequirementr0>0,andletk0 bethe i i i number of groups currently active. The leaves of g already covered in previous iterations are removed i from g; with a slight abuse of notation, we refer to this shrunk version of the group g also as g. All i i i theedgeschoseninpreviousiterationshavetheircostreducedtozero: weshouldnothaveto“pay”for these edges if we choose them again. For any non-root node u, let pe(u) denote the edge connecting u toitsparent;foranyedgeenotincidentontheroot,letpe(e)denotetheparentedgeofe. Finally,given anedgee=(u,v)whereuistheparentofv,bothT(v)andT(e)denotethesubtreeofGrootedatv. ThefollowingintegerprogrammingrelaxationfortheresidualproblemwasproposedbyKonjevod etal.[11]: Z∗=min(cid:229) c x e e e subjectto (cid:229) x =r0 ∀activeg (4.1) pe(j) i i j∈gi (cid:229) x ≤r0x ∀activeg,∀e∈E(T) (4.2) pe(j) i e i j∈(T(e)∩gi) x ≥x ∀enotincidentonr (4.3) pe(e) e x ∈[0,1] e Notethatforcingeachvariablex tohavevaluesin{0,1}insteadofvaluesintherealinterval[0,1]gives e us a ILP formulation of the Covering Steiner problem; indeed, in this case, the variable x being set to e 1correspondstotheedgeebeinginthesolutiontree. Sincewerelaxtheproblemandallowthex ’sto e takevaluesinalargerrange([0,1]insteadof{0,1}),itfollowsthattheoptimalvalueZ∗ ofthisLPisa lowerboundonOPT,theoptimalsolutionvalueoftheintegerlinearprogram,andhenceoftheoriginal CoveringSteinerinstance. Ineachiterationwestartwiththeresidualproblem,solvetheaboveLPoptimally,andthenroundthe resultingfractionalsolutionasdescribedbelowinSection4.2. Asnotedin[11],itisinterestingtonote that the integrality gap of the above relaxation can be quite large: when we write the LP relaxation for theoriginalinstance,theintegralitygapcanbearbitrarilyclosetoK. Henceitisessentialthatwesatisfy therequirementspartiallyineachiterationt,re-solvetheLPfortheresidualproblem,andcontinue. 4.2 RoundingtheFractionalSolution Let {x } denote an optimal solution to the LP relaxation for some generic iterationt, and let Z∗ be the e t optimal LP value. We now show how to round such an optimal solution to partially cover some of the residual requirements. In all of the discussion below, only currently active groups will be considered. For any leaf j, we call x the flow into j. The constraint (4.1) ensures that total flow into the leaves pe(j) of a group g is exactly r0. For α ≥1, we define a group g to be (p,α)-covered if a total flow of at i i i least pr0 goes into the elements (i.e., leaves) of g which receive individual flow values of at least 1/α. i i Anα-scalingofthesolution{x }isthescaled-upsolution{xˆ}wherewesetxˆ ←min{αx ,1},forall e e e e edgese. THEORYOFCOMPUTING,Volume2(2006),pp. 53–64 58 ANIMPROVEDAPPROXIMATIONRATIOFORTHECOVERINGSTEINERPROBLEM The iteration proceeds as follows. We define G to be the set of active groups that are (1/2,4)- 1 covered; i.e., at least half of the flow into these groups goes to elements that get individual flows of at leastaquarter. WewillconsidertwocasesbasedonwhetherthenumberofgroupsinG isatleastk0/2 1 ornot. Case I: |G |≥k0/2. In this case, we simply take a 4-scaling of the LP solution and pick the edges that 1 are rounded up to 1. By the monotonicity constraint x ≥x in the LP, the edges thus picked will pe(e) e formaconnectedsubtreecontainingtheroot. Moreover,weclaimthateverygroupinG hasatleasthalfofitsrequirementcoveredbythisprocess. 1 Indeed,anygroupg ∈G is(1/2,4)-covered(i.e.,ithasatleastr0/2ofitsmemberleavesreceivingflows i 1 i of value at least 1/4); hence the 4-scaling ensures that the picked edges cover at least r0/2. Since we i are in the case when G is large, we know that at least half of the currently active groups have their 1 requirements reduced by at least half. But now Lemma 3.1 for the chip game implies that the total numberofiterationswhereCaseIcanholdisatmostO(logk·logK). Furthermore,wepayacostofat most4·Z∗≤4·OPTineachsuchiterationt,implyingthefollowingresult: t Lemma4.1. ThetotalcostincurredinCase-Iiterations,where|G |≥k0/2,is 1 cost(CaseIiterations)=O(logk·logK·OPT). (4.4) (Letusemphasizeagainthatthroughoutthepaper,OPTreferstothecostoftheoptimalsolutionforthe originalCoveringSteinerinstance.) NowsupposeCaseIdoesnothold,andthusweconsider: Case II: |G | < k0/2; i.e., fewer than half the groups are (1/2,4)-covered. In this case, we further 1 categorizethegroupsinG\G asfollows. Letλ =c0logN,forasufficientlylargeabsoluteconstantc0. 1 WedefineG tobethesetofactivegroupsthatarenot (3/4,λ)-covered: i.e., atleastonefourthofthe 2 flow into these groups goes to elements that receive very little flow (at most 1/λ each). Finally, let G 3 bethesetofactivegroupsthatdonotlieinG ∪G . 1 2 We now use a modification of the rounding procedure used previously by Garg et al. [6] and Kon- jevodetal.[11]. Let{x0}beaλ-scalingoftheLPsolution;i.e.,x0 =min{λ·x ,1}foreache. Now,we e e e dothefollowingforeachedgeindependently: • Foreveryedgeeincidentontheroot,wepickewithprobabilityx0. e • Foreveryotheredgeewithitsparentdenoted f,pickewithprobabilityx0/x0. e f LetH denotethesubgraphofGinducedbytheedgesthatwerepicked;thesolutionwereturnisT ,the H connected subtree of H that contains the root r. We now set the costs of all chosen edges to 0, so as to not count their costs in future iterations. It is easy to verify that the probability of the event e∈T for H someedgeeisx0 (see,e.g.,[6,Lemma3.1]),andhencelinearityofexpectationimplies: e E[cost(T )]= (cid:229) x0 ≤λ· (cid:229) x =λ·OPT. (4.5) H e e e∈E e∈E We next analyze the expected coverage properties of this randomized rounding procedure. Let us firstconsideranyg ∈G ;bydefinition,g mustbe(3/4,λ)-covered,butnot (1/2,4)-covered. Inother i 3 i THEORYOFCOMPUTING,Volume2(2006),pp. 53–64 59 A.GUPTAANDA.SRINIVASAN words,ifweconsidertheleavesofg whoseindividualflowvalueslieintherange[1/λ,1/4],thetotal i flow into them is at least (3/4−1/2)r0 =r0/4. Since the flow into any one of these leaves is no more i i than 1/4, thereare at least r0 such leavesin thegroup g. Finally, since all theseleaves haveindividual i i flow values of at least 1/λ, all of them get chosen with probability 1 into our random subtree T , and H henceeverygroupinG hasallofitsrequirementsatisfiedwithprobability1. 3 This leaves us with groupsin G . For any suchgroup g ∈G , let g0 be the subset of elementsof g 2 i 2 i i whichhaveindividualin-flowvaluesofatmost1/λ,andlet f denotethetotalflowintotheelementsof i g0. ThefollowingfactfollowsfromtheverydefinitionofG . i 2 Fact4.2. Foranyg ∈G ,theflow f ≥r0/4. i 2 i i IfwedefineY foreachleaf j∈g0 tobetheindicatorvariableindicatingthat j waschosen, thenit ij i suffices to give a lower bound on X =(cid:229) Y , the number of elements of g0 that get covered by the i j∈g0 ij i i aboverandomizedrounding. Forthis,weplantoemployJanson’sinequality(Theorem2.1). Sinceeach of the flows f is at most 1/λ, the scaled-up value x0 (j)≤1 for each j∈g0 even after the λ-scaling, i. pe i andhence µ =E[X]=(cid:229) E[Y ]= fλ. WeneedafewfurtherdefinitionsinordertoapplyJanson’s i i j∈g0 ij i i inequality. LetA bethepathfromtheleaf j totherootr,andletA0 betheprefixofA ,theedgeseof j j j which satisfy x <1/λ. (When we say “prefix” here, we view A as starting from the leaf j and going e j up to the root r.) Note that in our rounding, the edges e of A which do not lie in A0 satisfy x ≥1/λ, j j e and hence will be chosen with probability 1. Thus,Y is 1 if and only if A0 is contained in the chosen ij j subtreeT . Nowfortwoleaves j,j0∈g0,wewilldefinetworelations: H i • j∼ j0 ifandonlyif(a) j6= j0 and(b)thepathsA ,A intersectinatleastoneedge;i.e.,theleast j j0 commonancestorof jand j0 inGisnottherootr. If j∼ j0,letlca(j,j0)denotetheleastcommon ancestraledgeof jand j0 inT0. • j ∼0 j0 if and only if (a) j 6= j0 and (b) the paths A0,A0 intersect in at least one edge. This is j j0 basically the same as the previous definition, except that we now work with the paths A0 instead j ofA . Alsonotethatif j∼0 j0,thenlca(j,j0)iswell-defined. j TouseJanson’sinequality,define x0 x0 D 0= (cid:229) pe(j) pe(j0) . (4.6) i x0 j,j0∈g0i: j∼0j0,xlca(j,j0)>0 lca(j,j0) It is easy to verify that this is indeed (cid:229) E[Y Y ]; indeed, if we condition on the eventY =1, we j∼0j0 ij ij0 ij know that the lca(j,j0) must be contained in T , and hence the conditional probability of the event H Y =1canbeshowntobex0 /x0 . Since f ≥r0/4byFact4.2,wegetr0≤4f =4µ/λ,which ij0 pe(j0) lca(j,j0) i i i i i isatmostµ/2ifc0 islargeenough. NowJanson’sinequalityshowsthat i Pr[X ≤r0]≤exp(cid:8)− µi/4 (cid:9) . (4.7) i i 2+D 0/µ i i LetusnowboundD 0,byconsideringthefollowingclosely-relatedquantity: i x x D = (cid:229) pe(j) pe(j0) . (4.8) i x j,j0∈g0i: j∼j0,xlca(j,j0)>0 lca(j,j0) THEORYOFCOMPUTING,Volume2(2006),pp. 53–64 60 ANIMPROVEDAPPROXIMATIONRATIOFORTHECOVERINGSTEINERPROBLEM ThewaysinwhichD differsfromD 0arethat: (i)thesumisoverpairs(j,j0)whichsatisfy j∼ j0,instead i i of j∼0 j0;and(ii)thesummandinvolvestermssuchasx insteadofx0 . pe(j) pe(j) Now,[11,Theorem3.2]showsthatD ≤r0(r0−1+r0lnN). Thereadercanverifythatanypair(j,j0) i i i i thatappearsinthesumforD 0,alsoappearsinD ;furthermore,foranysuchpair, i i x x x0 x0 pe(j) pe(j0) pe(j) pe(j0) =λ· . x x0 lca(j,j0) lca(j,j0) Thus, D 0 ≤λ·D , and hence D 0 =O((r0)2log2N), by [11, Theorem 3.2]. Now plugging this into (4.7), i i i i along with the facts µ = f λ = f c0logN and f ≥r0/4, we get that there is an absolute constant c00 ∈ i i i i i (0,1)suchthat Pr[X ≥r0]≥c00 . (4.9) i i Applyingthelinearityofexpectationto(4.9)showsusthattheexpectednumberofgroupsinG thatget 2 alloftheirrequirementcoveredinthisiterationisatleastc00·|G |. 2 Tosummarize,theexpectednumberofgroupswhoserequirementisfullycoveredisatleast c00·|G |+|G |≥c00·|G ∪G |≥c00k0/2 , 2 3 2 3 the last inequality holding since we are in Case II and G <k0/2. Applying Markov’s inequality gives 1 usthatwecoveraconstantfractionofthegroupswithconstantprobability,ensuringthattheprobability thatnotallgroupsaresatisfiedafteralogkiterationsinwhichCaseIIheldisatmost1/4(forsomelarge enougha). Also,summinguptheexpectedcost(4.5)overalliterations(usingthelinearityofexpectation),and thenusingMarkov’sinequality,weseethatwithprobabilityatleast1/2, cost(CaseIIiterations)=O(logk·logN·OPT) . (4.10) Combining(4.4)and(4.10)andnotingthatK ≤N,wegettheproofofTheorem1.1. 5 Open Questions It would be nice to resolve the approximability of the Group Steiner and Covering Steiner problems on general graph instances; we currently lose a logarithmic factor due to the step of approximating generalgraphsbydistributionsovertreemetrics. Asapracticalmatter,itwouldbeinterestingtoemploy frameworkssuchasthoseof[10]toapproximatelysolvethelinearprogrambycombinatorialmeans,or todevelopanewcombinatorialapproximationalgorithmmatchingourbounds. Acknowledgments We thank Eran Halperin, Goran Konjevod, Guy Kortsarz, Robi Krauthgamer, R. Ravi, and Nan Wang forhelpfuldiscussions. Wealsothanktherefereesfortheirmanyhelpfulcomments. THEORYOFCOMPUTING,Volume2(2006),pp. 53–64 61 A.GUPTAANDA.SRINIVASAN References [1] * YAIR BARTAL: Probabilistic approximations of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, pp. 184–193,1996. [FOCS:10.1109/SFCS.1996.548477]. 1 [2] * MOSES CHARIKAR, CHANDRA CHEKURI, ASHISH GOEL, AND SUDIPTO GUHA: Round- ing via trees: deterministic approximation algorithms for group Steiner trees and k median. In Proceedings of the 30th Annual Symposium on the Theory of Computing, pp. 114–123, 1998. [STOC:10.1145/276698.276719]. 1 [3] * GUY EVEN, GUY KORTSARZ, AND WOLFGANG SLANY: On network design problems: fixed cost flows and the covering Steiner problem. ACM Trans. Algorithms, 1(1):74–101, 2005. [TALG:10.1145/1077464.1077470]. 1 [4] * JITTAT FAKCHAROENPHOL, SATISH RAO, AND KUNAL TALWAR: A tight bound on ap- proximating arbitrary metrics by tree metrics. J. Comput. System Sci., 69(3):485–497, 2004. [JCSS:10.1016/j.jcss.2004.04.011]. 1 [5] * NAVEEN GARG: Saving an epsilon: a 2-approximation for the k-mst problem in graphs. In Proceedingsofthe37thAnnualACMSymposiumonTheoryofComputing, Baltimore, MD,USA, May22-24,2005,pp.396–402,2005. [STOC:10.1145/1060590.1060650]. 1 [6] * NAVEEN GARG, GORAN KONJEVOD, AND R. RAVI: A polylogarithmic approximation algorithm for the group Steiner tree problem. Journal of Algorithms, 37(1):66–84, 2000. [JAlg:10.1006/jagm.2000.1096]. 1,1,4.2 [7] * ERAN HALPERIN, GUY KORTSARZ, ROBERT KRAUTHGAMER, ARAVIND SRINIVASAN, AND NAN WANG: Integrality ratio for group Steiner trees and directed Steiner trees. In 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 275–284, January 2003. [SODA:644108.644155]. 1 [8] * ERAN HALPERIN AND ROBERT KRAUTHGAMER: Polylogarithmic inapproximability. In Pro- ceedings of the thirty-fifth ACM symposium on Theory of computing, pp. 585–594. ACM Press, 2003. [STOC:10.1145/780542.780628]. 1 [9] * SVANTE JANSON: Poisson approximation for large deviations. Random Structures and Algo- rithms,1(2):221–229,1990. 1.1,2 [10] *ROHITKHANDEKAR: LagrangianRelaxationbasedAlgorithmsforConvexProgrammingProb- lems. PhDthesis,IndianInstituteofTechnology,NewDelhi,March2004. 5 [11] *GORAN KONJEVOD, R. RAVI, AND ARAVIND SRINIVASAN: Approximationalgorithmsforthe coveringSteinerproblem. RandomStructuresandAlgorithms,20(3):465–482,2002. SpecialIssue onProbabilisticmethodsincombinatorialoptimization. [RSA:10.1002/rsa.10038]. 1,1,1.1,4.1, 4.1,4.2,4.2 THEORYOFCOMPUTING,Volume2(2006),pp. 53–64 62