Authors Anupam Gupta, Aravind Srinivasan,
License CC-BY-ND-2.0
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 53–64
http://theoryofcomputing.org
An Improved Approximation Ratio for the
Covering Steiner Problem∗
Anupam Gupta† Aravind Srinivasan‡
Received: August 4, 2005; published: February 17, 2006.
Abstract: In the Covering Steiner problem, we are given an undirected graph with edge-
costs, and some subsets of vertices called groups, with each group being equipped with a
non-negative integer value (called its requirement); the problem is to find a minimum-cost
tree which spans at least the required number of vertices from every group. The Covering
Steiner problem is a common generalization of the k-MST and the Group Steiner problems;
indeed, when all the vertices of the graph lie in one group with a requirement of k, we get
the k-MST problem, and when there are multiple groups with unit requirements, we obtain
the Group Steiner problem.
While many covering problems (e.g., the covering integer programs such as set cover)
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. Part of this work was done while the authors were at Lucent Bell Laboratories, 600-700 Mountain Avenue,
Murray Hill, NJ 07974-0636, USA.
† The research of this author was supported in part by a National Science Foundation CAREER award CCF-0448095, and
by an Alfred P. Sloan Fellowship.
‡ The research of this author was supported in part by the National Science Foundation under Grant No. 0208005 and ITR
Award CNS-0426683.
ACM Classification: C.2.0, F.2.2, G.1.6, G.3
AMS Classification: 68W20, 68W25, 90C59
Key words and phrases: Algorithms, Approximation Algorithms, Steiner Trees, Randomized Algo-
rithms, Network Design
Authors retain copyright to their work and grant Theory of Computing unlimited rights
to publish the work electronically and in hard copy. Use of the work is permitted as
long as the author(s) and the journal are properly acknowledged. For the detailed
copyright statement, see http://theoryofcomputing.org/copyright.html.
c 2006 Anupam Gupta and Aravind Srinivasan DOI: 10.4086/toc.2006.v002a003
A. G UPTA AND A. S RINIVASAN
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
Steiner problem.
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
Steiner problem given by Even et al. [3] and Konjevod et al. [11]. Our results match the approximation
guarantee of the known randomized algorithm for the Group Steiner problem due to Garg et al. [6]
(see the paper of Charikar et al. [2] for a deterministic algorithm). A suitable melding of a randomized
rounding approach with a deterministic “threshold rounding” method leads to our result.
Let G = (V, E) be an undirected graph with a non-negative cost function c defined on its edges. Let
a family G = {g1 , g2 , . . ., gk } of k subsets of V be given; we refer to these sets g1 , g2 , . . . , gk as groups.
For each group gi , a non-negative integer ri ≤ |gi | is also given, called the requirement of the group.
The Covering Steiner problem on G is to find a minimum-cost tree in G that contains at least ri vertices
from each group gi ; the special case of unit requirements (i.e., ri = 1 for all i) corresponds to the Group
Steiner problem. We denote the number of vertices in G by n, the size of the largest group by N, and the
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 ρ–
approximation algorithm on tree-instances implies an O(ρ log n)–approximation algorithm for arbitrary
instances. In fact, we can assume that the instance is a rooted tree instance where the root vertex must
be included in the tree that we output; this assumption can be discharged by running the algorithm over
all choices of the root and picking the best tree.
Given an instance of the Covering Steiner tree problem, one can get an O(k) approximation algo-
rithm using well-known ideas without resorting to the reduction to tree instances outlined above. Indeed,
one can use the 2-approximation algorithm (given by Garg [5]) for the rooted ri -MST on each group gi
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(log k · log N). For the Covering Steiner problem, the current-best approximation
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 53–64 54
A N I MPROVED A PPROXIMATION R ATIO FOR THE C OVERING S TEINER P ROBLEM
algorithm for tree instances is O((log k + log K) · log N) [3, 11]; also, an approximation bound of
log N · log2 k
O
log(2(log N) · (log k)/ log K)
2
is also presented in [11], which is better if K ≥ 2a(log k) where a > 0 is a constant. As mentioned above,
we need to multiply each of these three approximation bounds by O(log n) to obtain the corresponding
results for general graphs.
Note that the above approximation ratios get worse as the requirements increase, i.e., as K increases.
This is unusual for covering problems, where the approximability usually gets better as the coverage
requirements increase. This is well-known, for instance, in the case of covering integer programs which
include the set cover problem; the “multiple coverage” version of set cover is one where each element
of the ground set needs to be covered by at least a given number of sets. In particular, the approximation
ratio improves from logarithmic to O(1) (or even 1 + o(1)) for families of such problems where the min-
imum covering requirement B grows as Ω(log m), when m is the number of constraints (see, e.g., [12]).
In light of these results, it is natural to ask whether the approximation guarantee for the Covering Steiner
problem can be better than that for the Group Steiner problem.
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
root with edge-cost zero and add these leaves to all the groups. It is easily seen that any solution to this
Covering Steiner instance can be transformed to a solution to the original Group Steiner instance with
no larger cost, and that the two instances have the same optimal solution value. Therefore, the Covering
Steiner problem is at least as hard to approximate as the Group Steiner problem. (This fact was pointed
out to us by Robert Krauthgamer.)
We are thus led to the question: can the Covering Steiner problem be approximated as well as the
Group Steiner problem? The following theorem answers this question in the affirmative:
Theorem 1.1. There is a randomized polynomial-time approximation algorithm for the covering Steiner
problem which, with high probability, produces an feasible solution with an approximation ratio of (i)
O(log N · log k) for tree instances, and (ii) O(log n · log N · log k) for general instances.
This implies an improvement of Θ((log n)/ log log n) over previous results in some situations; in-
deed, this is achieved when, say, k = log2+Θ(1) n and K = nΘ(1) . (The reason we take k log2 n in this
example is that the problem on trees is approximable to within O(k) as noted earlier, and so if k was
small, we would have a good approximation algorithm anyway.)
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−ε )-
approximation algorithm for the Covering Steiner problem implies that NP ⊂ ZTIME[exp{(log n)O(1) }].
(Technically, the hardness is shown for the rooted version of the problem, but this is without loss of
generality, since the rooted version can be reduced to the unrooted version by introducing a new group
g0 containing only the root vertex r and having unit requirement.) Furthermore, since we adopt a natural
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 Ω(log k ·
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 53–64 55
A. G UPTA AND A. S RINIVASAN
log N/ log log N) [7]. Since this integrality gap naturally extends to the Covering Steiner problem as
well, this suggests that our techniques cannot improve the approximation guarantee substantially.
1.1 Our Techniques
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
fractional solution of the LP for the current residual problem, and extend the partial solution using either
a randomized rounding approach or a direct deterministic approach.
Informally, in order to do better than the approach of Konjevod et al. [11], the main technical issue we
handle is as follows. Let OPT denote the optimal solution value of a given tree instance. In essence, each
iteration of [11] adds an expected cost of O(OPT · log N) to the solution constructed so far, and reduces
the total requirement by a constant fraction (in expectation). Since the initial total requirement is at most
k · K, we thus expect to run for O(log k + log K) iterations, resulting in a total cost of O(OPT · (log k +
log K) log N) with high probability. To eliminate the log K term from their approximation guarantee, we
show, roughly, that every iteration has to satisfy one of two cases: either (i) a good fraction of the groups
have their requirement cut by a constant factor via a threshold rounding scheme, while paying only a
cost of O(OPT), or (ii) a randomized rounding scheme is expected to fully cover a constant fraction of
the groups. A chip game presented in Section 3 is used to bound the number of iterations where case (i)
holds; Janson’s inequality [9] and some deterministic arguments are used for case (ii). In the interest of
the cleanest exposition, we have not attempted to optimize our constants.
2 Preliminaries
The analysis of our algorithm will use an inequality due to Janson [9], which we now state. Let Ω
be a set of elements, and let us pick a random set R by picking each e ∈ Ω independently with some
probability pe . Let {A j ⊆ Ω | j ∈ J} be some family of subsets of Ω, and we say that j ∼ j0 if j 6= j0
/ Define B j to be the event that A j ⊆ R, and let ∆ = ∑ j< j0 : j∼ j0 Pr[B j ∩ B j0 ]. If Y j is the
and A j ∩ A j0 6= 0.
indicator variable for event B j , let µ j = E[Y j ] = Pr[B j ], and µ = ∑ j∈J µi . Then Janson’s inequality says
that
Theorem 2.1. For any δ ∈ [0, 1],
δ2 µ
Pr ∑ Y j ≤ (1 − δ )µ ≤ exp −
. (2.1)
j 2 + (∆/µ)
3 A Chip Game
Consider the following chip game. We initially have chips arranged in k groups, with each group gi
(init)
having some number ni ≤ K of chips. Chips are iteratively removed from the groups in a manner
described below; a group is called active if the number of chips in it is nonzero. The game proceeds in
rounds: in each round, we choose roughly half of the currently active groups and halve their sizes, until
there are no more active groups left. Formally, the game is as follows:
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 53–64 56
A N I MPROVED A PPROXIMATION R ATIO FOR THE C OVERING S TEINER P ROBLEM
1. At the start of some round, let ni denote the number of chips in group gi . Let A denote the number
of groups currently active; i.e., A = |{i | ni 6= 0}|.
2. We choose any set of at least dA/2e active groups.
3. For each of these chosen groups gi , we remove at least dni /2e chips, causing the new number
of chips in group gi to become at most bni /2c. Note that this may cause some of the groups to
become inactive.
4. If there are no more chips left, we stop, else we go back to Step 1.
In the analysis below, it will not matter that two constants in Steps 2 and 3 above were 1/2 each; any
two constants a, b ∈ (0, 1) lead to the same asymptotic result in the following lemma.
Lemma 3.1. The maximum number of rounds possible in the above chip game is O(log k · log K).
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 + blog ni c chips in each group gi ; once again, a group
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 N1 be the number of rounds in which at
least k/2 groups are active. In each of these rounds, at least k/4 chips get removed. However, since
the total number of chips is at most k(1 + log K), the number of such rounds N1 is at most 4(1 + log K).
Proceeding in this manner, we see that the total number of rounds is O(log k · log K), as claimed.
The proof above indicates how to prove that the bound proved above in Lemma 3.1 is tight, and there
are runs of the chip game which require Θ(log k · log K) rounds. Suppose all the groups start off with
exactly K chips. We first repeatedly keep choosing the same set of dk/2e groups for removing chips, and
do this until all these groups become inactive; we need Θ(log K) 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/4 active groups, until all of these become inactive. Proceeding in this manner, we can go for a total of
Θ(log k · log K) rounds.
4 The Algorithm and Analysis
In this section, we present our algorithm for the Covering Steiner problem, and analyse it. As mentioned
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
belonging to a group is a leaf of T , and that every leaf belongs to some group.
4.1 The Basic Approach
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
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 53–64 57
A. G UPTA AND A. S RINIVASAN
additional coverage not provided by the previous iterations. This process is continued until the required
coverage is accomplished, and the union of all the trees constructed is returned as output.
Consider a generic iteration; we will use the following notation. Let ri0 denote the residual require-
ment of group gi ; call the group gi active if and only if this residual requirement ri0 > 0, and let k0 be the
number of groups currently active. The leaves of gi already covered in previous iterations are removed
from gi ; with a slight abuse of notation, we refer to this shrunk version of the group gi also as gi . All
the edges chosen in previous iterations have their cost reduced to zero: we should not have to “pay” for
these edges if we choose them again. For any non-root node u, let pe(u) denote the edge connecting u
to its parent; for any edge e not incident on the root, let pe(e) denote the parent edge of e. Finally, given
an edge e = (u, v) where u is the parent of v, both T (v) and T (e) denote the subtree of G rooted at v.
The following integer programming relaxation for the residual problem was proposed by Konjevod
et al. [11]:
Z ∗ = min ∑ ce xe
e
subject to ∑ xpe( j) = ri0 ∀ active gi (4.1)
j∈gi
∑ xpe( j) ≤ ri0 xe ∀ active gi , ∀ e ∈ E(T ) (4.2)
j∈(T (e)∩gi )
xpe(e) ≥ xe ∀ e not incident on r (4.3)
xe ∈ [0, 1]
Note that forcing each variable xe to have values in {0, 1} instead of values in the real interval [0, 1] gives
us a ILP formulation of the Covering Steiner problem; indeed, in this case, the variable xe being set to
1 corresponds to the edge e being in the solution tree. Since we relax the problem and allow the xe ’s to
take values in a larger range ([0, 1] instead of {0, 1}), it follows that the optimal value Z ∗ of this LP is a
lower bound on OPT, the optimal solution value of the integer linear program, and hence of the original
Covering Steiner instance.
In each iteration we start with the residual problem, solve the above LP optimally, and then round the
resulting fractional solution as described below in Section 4.2. As noted in [11], it is interesting to note
that the integrality gap of the above relaxation can be quite large: when we write the LP relaxation for
the original instance, the integrality gap can be arbitrarily close to K. Hence it is essential that we satisfy
the requirements partially in each iteration t, re-solve the LP for the residual problem, and continue.
4.2 Rounding the Fractional Solution
Let {xe } denote an optimal solution to the LP relaxation for some generic iteration t, and let Zt∗ be the
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 xpe( j) the flow into j. The constraint (4.1) ensures that total flow into the leaves
of a group gi is exactly ri0 . For α ≥ 1, we define a group gi to be (p, α)-covered if a total flow of at
least pri0 goes into the elements (i.e., leaves) of gi which receive individual flow values of at least 1/α.
An α-scaling of the solution {xe } is the scaled-up solution {xˆe } where we set xˆe ← min{α xe , 1}, for all
edges e.
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 53–64 58
A N I MPROVED A PPROXIMATION R ATIO FOR THE C OVERING S TEINER P ROBLEM
The iteration proceeds as follows. We define G1 to be the set of active groups that are (1/2, 4)-
covered; i.e., at least half of the flow into these groups goes to elements that get individual flows of at
least a quarter. We will consider two cases based on whether the number of groups in G1 is at least k0 /2
or not.
Case I: |G1 | ≥ k0 /2. In this case, we simply take a 4-scaling of the LP solution and pick the edges that
are rounded up to 1. By the monotonicity constraint xpe(e) ≥ xe in the LP, the edges thus picked will
form a connected subtree containing the root.
Moreover, we claim that every group in G1 has at least half of its requirement covered by this process.
Indeed, any group gi ∈ G1 is (1/2, 4)-covered (i.e., it has at least ri0 /2 of its member leaves receiving flows
of value at least 1/4); hence the 4-scaling ensures that the picked edges cover at least ri0 /2. Since we
are in the case when G1 is large, we know that at least half of the currently active groups have their
requirements reduced by at least half. But now Lemma 3.1 for the chip game implies that the total
number of iterations where Case I can hold is at most O(log k · log K). Furthermore, we pay a cost of at
most 4 · Zt∗ ≤ 4 · OPT in each such iteration t, implying the following result:
Lemma 4.1. The total cost incurred in Case-I iterations, where |G1 | ≥ k0 /2, is
cost(Case I iterations) = O(log k · log K · OPT). (4.4)
(Let us emphasize again that throughout the paper, OPT refers to the cost of the optimal solution for the
original Covering Steiner instance.) Now suppose Case I does not hold, and thus we consider:
Case II: |G1 | < k0 /2; i.e., fewer than half the groups are (1/2, 4)-covered. In this case, we further
categorize the groups in G \ G1 as follows. Let λ = c0 log N, for a sufficiently large absolute constant c0 .
We define G2 to be the set of active groups that are not (3/4, λ )-covered: i.e., at least one fourth of the
flow into these groups goes to elements that receive very little flow (at most 1/λ each). Finally, let G3
be the set of active groups that do not lie in G1 ∪ G2 .
We now use a modification of the rounding procedure used previously by Garg et al. [6] and Kon-
jevod et al. [11]. Let {xe0 } be a λ -scaling of the LP solution; i.e., xe0 = min{λ · xe , 1} for each e. Now, we
do the following for each edge independently:
• For every edge e incident on the root, we pick e with probability xe0 .
• For every other edge e with its parent denoted f , pick e with probability xe0 /x0f .
Let H denote the subgraph of G induced by the edges that were picked; the solution we return is TH , the
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 ∈ TH for
some edge e is xe0 (see, e.g., [6, Lemma 3.1]), and hence linearity of expectation implies:
E[cost(TH )] = ∑ xe0 ≤ λ · ∑ xe = λ · OPT. (4.5)
e∈E e∈E
We next analyze the expected coverage properties of this randomized rounding procedure. Let us
first consider any gi ∈ G3 ; by definition, gi must be (3/4, λ )-covered, but not (1/2, 4)-covered. In other
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 53–64 59
A. G UPTA AND A. S RINIVASAN
words, if we consider the leaves of gi whose individual flow values lie in the range [1/λ , 1/4], the total
flow into them is at least (3/4 − 1/2)ri0 = ri0 /4. Since the flow into any one of these leaves is no more
than 1/4, there are at least ri0 such leaves in the group gi . Finally, since all these leaves have individual
flow values of at least 1/λ , all of them get chosen with probability 1 into our random subtree TH , and
hence every group in G3 has all of its requirement satisfied with probability 1.
This leaves us with groups in G2 . For any such group gi ∈ G2 , let g0i be the subset of elements of gi
which have individual in-flow values of at most 1/λ , and let fi denote the total flow into the elements of
g0i . The following fact follows from the very definition of G2 .
Fact 4.2. For any gi ∈ G2 , the flow fi ≥ ri0 /4.
If we define Yi j for each leaf j ∈ g0i to be the indicator variable indicating that j was chosen, then it
suffices to give a lower bound on Xi = ∑ j∈g0i Yi j , the number of elements of g0i that get covered by the
above randomized rounding. For this, we plan to employ Janson’s inequality (Theorem 2.1). Since each
of the flows fi is at most 1/λ , the scaled-up value xpe 0 ( j) ≤ 1 for each j ∈ g0 even after the λ -scaling,
i
.
and hence µi = E[Xi ] = ∑ j∈g0i E[Yi j ] = fi λ . We need a few further definitions in order to apply Janson’s
inequality. Let A j be the path from the leaf j to the root r, and let A0j be the prefix of A j , the edges e of
which satisfy xe < 1/λ . (When we say “prefix” here, we view A j as starting from the leaf j and going
up to the root r.) Note that in our rounding, the edges e of A j which do not lie in A0j satisfy xe ≥ 1/λ ,
and hence will be chosen with probability 1. Thus, Yi j is 1 if and only if A0j is contained in the chosen
subtree TH . Now for two leaves j, j0 ∈ g0i , we will define two relations:
• j ∼ j0 if and only if (a) j 6= j0 and (b) the paths A j , A j0 intersect in at least one edge; i.e., the least
common ancestor of j and j0 in G is not the root r. If j ∼ j0 , let lca( j, j0 ) denote the least common
ancestral edge of j and j0 in T 0 .
• j ∼0 j0 if and only if (a) j 6= j0 and (b) the paths A0j , A0j0 intersect in at least one edge. This is
basically the same as the previous definition, except that we now work with the paths A0j instead
of A j . Also note that if j ∼0 j0 , then lca( j, j0 ) is well-defined.
To use Janson’s inequality, define
0
xpe( 0
j) xpe( j0 )
∆0i = ∑ 0
xlca(
. (4.6)
j, j0 ∈g0i : j∼0 j0 , xlca( j, j0 ) >0 j, j0 )
It is easy to verify that this is indeed ∑ j∼0 j0 E[Yi j Yi j0 ]; indeed, if we condition on the event Yi j = 1, we
know that the lca( j, j0 ) must be contained in TH , and hence the conditional probability of the event
0 0 0 0
Yi j0 = 1 can be shown to be xpe( j0 ) /xlca( j, j0 ) . Since f i ≥ ri /4 by Fact 4.2, we get ri ≤ 4 f i = 4 µi /λ , which
is at most µi /2 if c0 is large enough. Now Janson’s inequality shows that
µi /4
Pr[Xi ≤ ri0 ] ≤ exp −
. (4.7)
2 + ∆0i /µi
Let us now bound ∆0i , by considering the following closely-related quantity:
xpe( j) xpe( j0 )
∆i = ∑ xlca( j, j0 )
. (4.8)
j, j0 ∈g0 : j∼ j0 , x
i 0 >0 lca( j, j )
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 53–64 60
A N I MPROVED A PPROXIMATION R ATIO FOR THE C OVERING S TEINER P ROBLEM
The ways in which ∆i differs from ∆0i are that: (i) the sum is over pairs ( j, j0 ) which satisfy j ∼ j0 , instead
of j ∼0 j0 ; and (ii) the summand involves terms such as xpe( j) instead of xpe(
0
j) .
Now, [11, Theorem 3.2] shows that ∆i ≤ ri (ri − 1 + ri ln N). The reader can verify that any pair ( j, j0 )
0 0 0
that appears in the sum for ∆0i , also appears in ∆i ; furthermore, for any such pair,
0
xpe( 0
xpe( j) xpe( j0 ) j) xpe( j0 )
=λ· 0 .
xlca( j, j0 ) xlca( j, j0 )
Thus, ∆0i ≤ λ · ∆i , and hence ∆0i = O((ri0 )2 log2 N), by [11, Theorem 3.2]. Now plugging this into (4.7),
along with the facts µi = fi λ = fi c0 log N and fi ≥ ri0 /4, we get that there is an absolute constant c00 ∈
(0, 1) such that
Pr[Xi ≥ ri0 ] ≥ c00 . (4.9)
Applying the linearity of expectation to (4.9) shows us that the expected number of groups in G2 that get
all of their requirement covered in this iteration is at least c00 · |G2 |.
To summarize, the expected number of groups whose requirement is fully covered is at least
c00 · |G2 | + |G3 | ≥ c00 · |G2 ∪ G3 | ≥ c00 k0 /2 ,
the last inequality holding since we are in Case II and G1 < k0 /2. Applying Markov’s inequality gives
us that we cover a constant fraction of the groups with constant probability, ensuring that the probability
that not all groups are satisfied after a log k iterations in which Case II held is at most 1/4 (for some large
enough a).
Also, summing up the expected cost (4.5) over all iterations (using the linearity of expectation), and
then using Markov’s inequality, we see that with probability at least 1/2,
cost(Case II iterations) = O(log k · log N · OPT) . (4.10)
Combining (4.4) and (4.10) and noting that K ≤ N, we get the proof of Theorem 1.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
general graphs by distributions over tree metrics. As a practical matter, it would be interesting to employ
frameworks such as those of [10] to approximately solve the linear program by combinatorial means, or
to develop a new combinatorial approximation algorithm matching our bounds.
Acknowledgments
We thank Eran Halperin, Goran Konjevod, Guy Kortsarz, Robi Krauthgamer, R. Ravi, and Nan Wang
for helpful discussions. We also thank the referees for their many helpful comments.
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 53–64 61
A. G UPTA AND A. S RINIVASAN
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] * M OSES C HARIKAR , C HANDRA C HEKURI , A SHISH G OEL , AND S UDIPTO G UHA: 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] * G UY E VEN , G UY KORTSARZ , AND W OLFGANG S LANY: 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] * J ITTAT FAKCHAROENPHOL , S ATISH R AO , AND K UNAL 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 G ARG: Saving an epsilon: a 2-approximation for the k-mst problem in graphs. In
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA,
May 22-24, 2005, pp. 396–402, 2005. [STOC:10.1145/1060590.1060650]. 1
[6] * NAVEEN G ARG , G ORAN KONJEVOD , AND R. R AVI: 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] * E RAN H ALPERIN , G UY KORTSARZ , ROBERT K RAUTHGAMER , A RAVIND S RINIVASAN ,
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] * E RAN H ALPERIN AND ROBERT K RAUTHGAMER: 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] * S VANTE JANSON: Poisson approximation for large deviations. Random Structures and Algo-
rithms, 1(2):221–229, 1990. 1.1, 2
[10] * ROHIT K HANDEKAR: Lagrangian Relaxation based Algorithms for Convex Programming Prob-
lems. PhD thesis, Indian Institute of Technology, New Delhi, March 2004. 5
[11] * G ORAN KONJEVOD , R. R AVI , AND A RAVIND S RINIVASAN: Approximation algorithms for the
covering Steiner problem. Random Structures and Algorithms, 20(3):465–482, 2002. Special Issue
on Probabilistic methods in combinatorial optimization. [RSA:10.1002/rsa.10038]. 1, 1, 1.1, 4.1,
4.1, 4.2, 4.2
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 53–64 62
A N I MPROVED A PPROXIMATION R ATIO FOR THE C OVERING S TEINER P ROBLEM
[12] * A RAVIND S RINIVASAN: New approaches to covering and packing problems. In Proceedings of
the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001), pp.
567–576, Philadelphia, PA, 2001. SIAM. [SODA:365411.365535]. 1
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 53–64 63
A. G UPTA AND A. S RINIVASAN
AUTHORS
Anupam Gupta
Computer Science Department
Carnegie Mellon University
Pittsburgh, PA 15232, USA
anupamg cs cmu edu
http://www.cs.cmu.edu/~anupamg
Aravind Srinivasan
Department of Computer Science and University of Maryland Institute for Advanced Com-
puter Studies
University of Maryland at College Park
College Park, MD 20742, USA
srin cs umd edu
http://www.cs.umd.edu/~srin
ABOUT THE AUTHORS
A NUPAM G UPTA is a faculty member at Carnegie Mellon University, Pittsburgh PA. He
grew up in Calcutta, India, went to the Indian Institute of Technology at Kanpur for his
B. Tech. degree, and received his Ph. D. from the University of California at Berkeley
under the guidance of Alistair Sinclair. He also spent two years searching for good and
unknown restaurants in New York while he was ostensibly a postdoctoral researcher
at Lucent Bell Labs, Murray Hill, NJ. Anupam’s interests include approximation algo-
rithms, metric embeddings, networking, eating, and playing squash badly.
A RAVIND S RINIVASAN is a faculty member at the University of Maryland, College Park.
He received his Ph. D. degree from Cornell University under the supervision of David
Shmoys, and his undergraduate degree from the Indian Institute of Technology, Madras.
His research interests are in randomized algorithms, networking, social networks, com-
binatorial optimization, and related areas. Aravind is a native of Chennai, India, and his
“mother tongue” (native language) is Tamil.
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 53–64 64