An Approximation Algorithm for the Covering Steiner Problem

The covering Steiner tree problem is a common generalization of the k-MST and the group Steiner problems: Given an edge weighted graph, with subsets of vertices called the groups, and a requirement for each group which is an integer of value at most the si

An Approximation Algorithm for the Covering Steiner ProblemGoran Konjevod R. Ravi

y

The covering Steiner tree problem is a common generalization of the k-MST and the group Steiner problems: Given an edge weighted graph, with subsets of vertices called the groups, and a requirement for each group which is an integer of value at most the size of the group, the problem is to nd a minimum-weight tree such that for each group, at least as many nodes as its requirement are included in the tree. When all requirements are equal to 1, we get the group Steiner problem, while if there is only group whose node set is all the vertices in the graph, and this group's requirement value is the integer k, the problem reduces to nding a minimum-weight tree containing k vertices. We present a polylogarithmic approximation algorithm for this problem which uses an integer linear programming formulation, and rounds the optimal fractional solution iteratively. One interesting feature of our algorithm is that even though the optimal fractional value of the original LP formulation may be a very bad estimate of the optimal integral solution value, at least one of the formulations arising in one of the iterations of our rounding estimates the optimal integral solution value well.

Abstract

de ned on the edges. Let g1;:::; gm V be subsets of vertices. We call the sets gi groups. For each group gi a nonnegative integer ki, called the requirement of the group is speci ed - this value for group i is at most jgi j. The covering Steiner problem on G is the problem of nding a minimum-cost connected subgraph of G which contains at least ki vertices of group gi for all i 2 f1;:::mg. We denote the size of the largest group by N, and the largest requirement of a group by K . We call the group vertices terminals. The covering Steiner problem generalizes two di erent NP-hard network design problems that have beenDept. of Math. Sciences, Carnegie Mellon University, Pittsburgh, PA 15213-3890. Work partly done at Los Alamos National Laboratory. Supported by the NSF CAREER grant CCR-9625297 and the DOE Contract W-7405-ENG-36. Carnegie Mellon University, Pittsburgh, PA 152133890. Work partly done while visiting IBM SRC, New Delhi. Supported by the NSF CAREER grant CCR-9625297. ravi@cmu.edukonjevod@andrew.cmu.edu

1 Introduction 1.1 Statement of the problem. Let G= (V; E ) be an undirected graph with a cost function c: E ! R+

studied recently, namely the k-MST problem (see Ravi, Sundaram, Marathe, Rosenkrantz and Ravi 16], Fischetti, Hamacher, J rnsten and Ma oli 9], Blum, Ravi and Vempala 6], and Garg 10]), and the group Steiner problem (see Reich and Widmayer 17], Garg, Konjevod and Ravi 12] and Charikar, Chekuri, Goel and Guha 7]). The k-MST problem is that of nding a minimumcost connected subgraph that contains at least k nodes in an undirected graph with nonnegative costs on edges. The covering Steiner problem reduces to the k-MST problem when there is only one group a

nd when all the vertices in V belong to this group. This problem is NP-hard and the best-known approximation ratio for this problem currently is 2, using an algorithm of Garg 11], but see also papers of Arya and Ramesh 3] and Arora and Karakostas 2]. This problem is solvable in polynomial time in some special cases, e.g. if the underlying graph is a tree. The group Steiner problem is the restriction of the covering Steiner problem where all group requirements are 1. This problem is at least as hard to approximate as the set cover problem, because even the special case where the underlying graph is a star-tree contains the set cover problem (Klein and Ravi 14]). Approximation algorithms for the group Steiner problem with polylogarithmic approximation ratios were presented in 12] (randomized) and 7] (deterministic). proximation algorithm for the covering Steiner problem on a tree with an approximation guarantee of O(log N log m log K ) Here, N denotes the maximum size of a group (which in turn is at most n, the total number of nodes), K denotes the maximum requirement value of any group (which in turn is at most N ) and m denotes the number of groups. For the group Steiner problem where K= 1, this approximation ratio matches the best-known ratio. We can transform the problem in any metric to one on a tree, with a worsening in the performance ratio, by using the technique of Bartal 5] and Charikar, Chekuri, Goel and Guha 7]. This then leads to an approximation algorithm for the general covering Steiner problem with approximation guarantee of O(log n log log n log N log m log K ). Using im1

1.2 Results. Our central result is a randomized ap-

y GSIA,

The covering Steiner tree problem is a common generalization of the k-MST and the group Steiner problems: Given an edge weighted graph, with subsets of vertices called the groups, and a requirement for each group which is an integer of value at most the si

proved metric approximations for graphs that exclude Ks;s as a minor (such as planar graphs, points in the plane), we can get an improved approximation guarantee for the problem on such graphs. Our algorithms can be derandomized by using ideas from 7]. ering Steiner problem on the tree by successively rounding solutions to linear programming relaxations of log K di erent covering Steiner subproblems that arise from our original problem. Our formulations capture the multiplicity requirement for the groups by using a di erent\commodity" to denote di erent unit requirements. Intuitively, each group is required to participate (include one of its vertices) in as many commodities as its requirement value. All vertices included in a commodity must be connected to the root via a subtree of edges that is chosen by the solution. The objective is to minimize the total cost of the edges chosen to support the trees for all commodities. Since a rounding step can only ensure that a constant fraction of each group's current requirement is met with high probability, we set up a new LP to satisfy the remaining requirement and proceed iteratively until all requirements are met. One surprising outcome is that the initial LP relaxation that we use for the original problem does not necessarily provide a good lower bound

on the cost of the optimal covering Steiner tree (See Section 2.3). Even for the special case with only one group whose requirement is K, the gap between the optimal integral and fractional solutions can be (K ). However, it follows from our proof that at least one of the O(log K ) LP relaxations we use in the rounding provides a good lower bound (within polylogarithmic factor of optimal).

1.3 Overview and contributions.We solve the cov-

(4) Every vertex of degree 1 belongs to some group (otherwise it may be removed from the graph); (5) It su ces to consider the rooted problem where we know one vertex called the root that belongs to the optimal solution (the algorithm may be run for each possible choice of this vertex).Steiner problem on a tree as an integer linear program. Let the indicator variable xe denote whether the edge e is contained in the solution, Then the cost of a solution P x equals e2E ce xe . In addition to x we use variables yi for i 2 f1;:::; K g. We may think of the variables yi as supporting ows of di erent commodities from the root to the terminals. In a covering Steiner tree, there are ki vertices of the group gi, so we require the commodities c1;:::; cki to each send a unit of ow from the root to some unique terminal in group gi, for all i. The nal solution x must majorize every yi . In addition, we must require that no terminal in a group be used by more than one commodity for this group. To ensure this, for each edge e incident on a terminal (pendant edge), we require that X

2.2 ILP Formulation. We formulate the covering

xe

2 Linear programming formulation

This constraint (or rather the fact that it can only be enforced for pendant edges) necessitates another set of constraints: xe xf for all successor edges f of e in the tree, for all e. This in turn makes our formulation possible only when G is a tree. The complete linear programming formulation follows. Here,@S denotes the set of edges with exactly P one endpoint in S, and yi (E 0 ) denotes e2E yi (e) for any subset of edges E 0 .0

i

i ye:

First, we make several assumptions that do not reduce the generality of the problem, but make it easier to formulate.

min

X

yi (@S ) 1

e2E

ce xe

results of Bartal 5] on probabilistic approximation of general metrics by tree metrics to reduce the original problem to the problem in a weighted tree with a (2.1) slight loss in the performance ratio| the details are in Section 4.1); (2) The groups are disjoint (a vertex belonging to several groups may be expanded into a star with edges of cost 0 and each leaf belonging to exactly one of the groups); (3) Every vertex belonging to a group has degree 1 (similar to the construction in (2)); 2

2.1 Assumptions. We assume the following. (1) The graph G is a weighted tree (we can use the

i xe ye

for all S V such that r 2 S and i such that for some group g, S\ g=; and kg i for all non-pendant edges eX

xe

xe xf

for all pendant edges e

i

i ye

for all (e; f

) where e is the parent of f 0 xe 1 8e:

The covering Steiner tree problem is a common generalization of the k-MST and the group Steiner problems: Given an edge weighted graph, with subsets of vertices called the groups, and a requirement for each group which is an integer of value at most the si

2.3 Integrality gap. Even for the version of the of e on the path from the root. This experiment isproblem with a single group, this linear formulation does not give a tight relaxation. For instance, let G be the tree in Fig. 1, that consists of a star with k? 1 leaves, whose center is connected to another star with k leaves by a single edge. Let the center of the rst star be the root of the tree. Denote the rst star by A, the second by B, and the edge joining them by e0 . The single group consists of all the leaves of G and has requirement value k. Consider the solution to the linear program where each commodity sends 1=k of ow from the root to each of the k? 1 leaves of A and each of the k di erent commodities sends 1=k of ow to a distinct leaf of B . The packing constraints force xe= 1 for all edges e in A, but since only one commodity is served by every edge of B, xf= 1=k for all edges f of B and for the edge e0 . 1 2

performed for each edge of G independently. Let H denote the subgraph of G induced by the chosen edges. We discard all connected components of H except the one containing the root, and denote the resulting tree by T . It is not di cult to see that the expected cost of a tree obtained in this experiment is equal to the cost of the initial linear programming solution. An edge e is included in T i all the edges in the path from r to e, say e1;:::; ep; e are picked in their respective independent random experiments, the probability of which is

xe1 xe2 1 xe1

xe xep= xe:

k r CFigure 1. 1 .. B . 2

A ... k?1

Garg, Konjevod and Ravi 12] further show that for each group g, the probability that a vertex of g is included in T is (1= log jgj). For this, they use an inequality of Janson 13]. By a similar argument, and using a generalization of the same inequality, we show that for each group, the probability that at least half of its requirement is satis ed by T is (1= log jgj).Theorem 3.1. Let T be the tree arising from the random experiment described above. Then there exists a constant C such that for any group g of size jgj and with requirement kg,

Let the cost of the edges belonging to the stars A and B be, and the cost of edge e0 be C . Clearly, the cost of the optimal tree that contains the root and covers k terminals is at least C+ k, since at least one of the leaves of B must be included. However, the relaxed solution described above costs only C=k+ k . Thus, the ratio between the optimal integral and fractional solutions of the formulation (2.1) can be as large as k.

Pr T contains at least kg=2 vertices of g] C log1jgj: In what follows we consider the experiment for a single group g with requirement k. First we state the probabilistic inequality: let be a universal set, and R determined by the experiment in which each element r 2 is independently included in R with probability pr . Let Ai be subsets of, and denote by Bi the event that Ai R. WriteP j if Bi and

i Bj are not independent. De ne= i PPr Bi\ Bj] j (the sum is over ordered pairs). Let X= i Xi, where Xi is an indicator variable for the event Bi, and let P= E X]= i Pr Bi].

3 The Iterative Rounding Algorithm

The algorithm runs in log K phases where K is the maximum requirement value. In each phase, a linear program is solved and the solution rounded to a set of edges of G. The rounded solution halves the residual requirement for every group and is then used to modify the problem whose LP formulation is solved in the next Theorem 3.2. (Janson's inequality 13].) With the notation as above, phase. The rounding procedure in each phase succeeds 2 with probability at least 1? 1=2 log K, and so the whole Pr X (1? ) e?=(2+ ): algorithm succeeds with probability at least 1=2. In our application,= E (T 0 ), and pe= xe=xp(e) 3.1 Basic rounding step. Suppose we are given where p(e) is the parent or predecessor of e on the path an optimal solution to the linear program (2.1). We from r. The subsets Ai are edge-sets of paths from r to use the rounding procedure described in 12], namely, leaves belonging to a xed group g, and X is the number an edge e is included in the set of edges chosen with of vertices of the group chosen in the experiment. probability xe=xp(e), where p(e) denotes the predecessor The following lemma was used in 12]. 3

The covering Steiner tree problem is a common generalization of the k-MST and the group Steiner problems: Given an edge weighted graph, with subsets of vertices called the groups, and a requirement for each group which is an integer of value at most the si

i i Lemma 3.3. If T and T 0 are trees that di er only in (i.e., ve is ye rounded down to the nearest power of the capacity of one edge e, so that xT (e) xT (e), then 10=11).

for any group, g, the probability of including a vertex from g is no greater in T 0 than in T . This lemma still holds in the covering Steiner problem, if the probability of including a vertex from g is replaced by the probability of including at least k=2 vertices of g, where k is the requirement of g. Another useful observation is the following. Lemma 3.4. Let x be the solution of the linear program (2.1) where a ow of 1 can be sent to vertices of group g by each of k di erent commodities. Then the expected number of vertices of g picked in one rounding step is at least k. In 12] it is shown (in the proof of their Theorem 3.2) that, given a solution x of the linear programming relaxation of the group Steiner problem, for every group g, there is a tree T g with capacities xg such that (1) the probability of success for g when rounding according to xg (that is, the probability of including a vertex of g) is (1= log jgj) and (2) the probability of success for g when rounding according to xg is no more than the probability of success when rounding according to x. Essentially, T g is obtained by rounding down the capacities to powers of 2, discarding the edges with capacity less than 1=(2n) and contracting the edges preceded by edges of equal capacities (except for the pendant edges). In the resulting tree, there is still a ow of 1=4 from the root to every group. We need a slightly di erent result now, because we must guarantee to c

over at least a half of a group's requirement. To be able to apply Theorem 3.2, we must keep the expected number of vertices of a group covered by a single rounding step a constant fraction above 1=2. We arrange the constants used in the rst part of the argument so that the expected number of vertices of g covered in a single rounding step is 2k=3, where k is the requirement of the group g. Now we can describe the proof of Theorem 3.1. Proof. (of Theorem 3.1.) Let g be a group with requirement k. Consider an optimal solution to the linear program (2.1) and its support tree. Let T be the tree spanned by the paths between the root and the vertices of g, and let (x; y) be the restriction of the optimal LP solution to the edges of T . For every i 2 f1;:::; kg and every e 2 E (T ) let i ve= (10=11)`; where` is chosen so that i (10=11)` ye< (10=11)`+1

0

Then de ne w, starting from the pendant edges and going up the tree T . For a pendant edge e, let

we=

k X i=1

i ve:

If w has been de ned for all children of a non-pendant edge f, let 1 h= maxfwe j f child of eg; 2 i h= 1maxk ve i and

wh= maxf 1; 2 g: h h Next, for every edge e, let ue= (10=11)` where` is chosen so that (10=11)` we< (10=11)`+1 (i.e., ue is we rounded down to the nearest power of 10=11). For every edge e such that 0< ue< 1=(121n), de ne ue= 0 and thus e ectively remove e from T . Finally, for every pair (e; f ) of edges such that e is a parent of f, f is not pendant and ue= uf, contract f . Call the resulting tree T 0. We use the following properties of T 0 .

(1) In one rounding step performed according to the

values of u, the probability of picking at least k=2 vertices of g is no greater than the probability of picking at least k=2 vertices of g when rounding according to x. (2) The expected number of vertices of g picked in one rounding step done according to u is at least 3k=4. (3) The depth of T 0 is d dlog11=10 ne. Property (1) follows from Lemma 3.3. Let p be the probability of success (picking at least k=2 vertices of g) in one step of rounding according to x. Let p1 and p2 be the respective probabilities of success when the rounding is done according to w and u. Then Property (1) claims that Since v y (v is just y rounded down), and since w and x are obtained respectively from v and y by the same

p p2:

monotone process (compare LP (2.1) to the de nition of w above), it follows that w x. Thus p p1 . To prove that p1 p2, note that removing some subtrees (consisting of edges of very small value) only decreases the success probability, and that the contractions described above do not change the probability of picking any vertex in a rounding step. Thus we have

p p 1 p2:4 To see that Property (2) holds, notice that converting y to v reduces the ow of each commodity by at most

The covering Steiner tree problem is a common generalization of the k-MST and the group Steiner problems: Given an edge weighted graph, with subsets of vertices called the groups, and a requirement for each group which is an integer of value at most the si

1=11. Furthermore, a fraction 1=11 of this ow may be substituting the upper bound for in Theorem 3.2 gives lost in rounding w to u, leaving behind at least (10=11)2 Pr at

least k=2 vertices of g are covered ow for each commodity. Finally, deleting edges with= Pr X (1? 1=3) 3k=4] u-value at most 1=(121n) reduces this ow by at most ! 1 1=121, leaving at least (10=11)2? 1=121> 3=4 ow for 9> 1? exp each commodity. Property (2) then follows from linear2+ 200k2 log jgj ity of expectation. ! 1 Property (3) is true because ue 11uf=10 when= 1? exp 2 8009k2 log jgj ever e is a parent edge of f, except possibly when f is+ 2 a pendant edge. ! 1 Denote by X the random variable that counts the 9= 1? exp 8 12800 log jgj vertices of g included in T after rounding. To apply+ 3k 9 Theorem (3.2), we need an upper bound on the value 1 .= 1? exp 24 Let a(e; f ) denote the least common ancestor of the k+ 12800 log jg j pair of pendant edges e and f, both belonging to group C> log jgj; g. For an edge f, let i(f ) denote the index i for which i maxi vf is achieved. Let d be the depth of the support for a suitably chosen C . tree of x. Then,=i ue uf X u X k maxi vf e e e f e ua(e;f ) f e ua(e;f ) i X X vf(f ) 11 kd X u k ue e i(f ) e e f e va(e;f ) 10XX

3.2 Ampli cation. After the basic rounding step described above, with probability at least C= log jgj we have satis ed a half of g's requirement. If we perform C log jgj rounding steps independently, with probabilityat least 1=e, at least one of them will succeed.

11 2 2 10 k log11=10 jgj 200k log jgj:

The rst inequality follows since f is a pendant edge going to a terminal node ofP group g whose requirement i i value is k, so that uf= k=1 vf k maxi vf . The i i second inequality uses the LP inequality uh vh for a non-pendant edge h and any commodity i. The third inequality follows from the proof of Theorem 3.2 in 12]. The most important observation is thati vf i f 2E (e;a) vaX

11; 10

3.3 Union. To ensure that we cover at least a half of every group's requirement, and that our iterative algorithm succeeds with a reasonable probability, we repeat the rounding a few more times. The goal is to bring down the probability of failure (to cover a half of the required number of vertices) for any group to 1=(2m log K ). Then by the union bound, we will have covered a half of every group's requirement with probability at least 1=(2 log K ). Recall that we write N for the size of the largest group and K for the maximum requirement. We repeat the basic rounding step C log N log 2m times, where satis es C ( log 2m log N )=C< 1: 1? log N 2m log K Since 1=e< 1=2, the above equation is implied by

1 1 where the E (e; a) is the set of all pendant edges f such< 2m log K; 2m that the least common ancestor of f and e is a. This P i=y i 1 for all commodities which is true whenever follows because f 2E(e;a) yf a i, and because vi was obtained from yi (which satis ed log> log 2m+ 2m log K: the ow-conservation constraints) by rounding down to log powers of 10=11. By Property (3), the expected number of vertices This gives of g covered in one rounding step is at least=

3kg=4. 1 We need to cover k=2 vertices, so let= 1=3. Now C log N (log 2m+ log log K ) 5

The covering Steiner tree problem is a common generalization of the k-MST and the group Steiner problems: Given an edge weighted graph, with subsets of vertices called the groups, and a requirement for each group which is an integer of value at most the si

as the number of basic rounding steps needed. We may assume that log log K< log 2m. Indeed, otherwise we have 2m< log K so there are no more than O(log n) groups and just taking a 2-optimal k-MST 11] for each of them gives an O(log n) approximation algorithm for the overall problem. Thus we repeat the basic rounding step O(log N log 2m) times and ensure that a half of every group's requirement is covered with probability at least 1? 1=(2 log K ).

3.4 Iteration. To achieve the required coverage for every group, we can repeat the above rounding algorithm on a sequence of subproblems of the original covering problem, at each step halving the residual requirement. Suppose the rst rounding phase succeeded in covering a half of the requirement for every group. Then we modify the graph by contracting the chosen edges and reducing the number of commodities that support group g to at most kg=2 for every g. Note that any integral solution to the original problem contains as a subgraph an integral solution to this residual problem. Therefore, the cost of the optimal fractional solution to the residual problem is a lower bound on the cost of the optimal solution to the original problem. In this way, we solve a sequence of log K subproblems, and then form the solution of the original problem as the union of the solutions to the subproblems. If any of the log K steps fails, we stop the algorithm and say the algorithm fails. Since the probability of success of each step is at least 1? 1=2 log K, and the events are independent, the algorithm succeeds with p probability at least 1= e> 1=2.formed= O(log N log K log m) times, and so by Markov's inequality, Pr solution costs more than 4 OPT]< 1=4; where OPT denotes the minimum cost of a covering Steiner tree. Thus, with probability more than 1=2 both\good" events happen, that is we get a feasible solution of cost at most 4 OPT . Theorem 3.5. There is a randomized polynomial time algorithm that, with probability at least 1=2, nds a covering Steiner tree on an underlying graph which is a tree, of cost O(log N log m log K ) times the minimum. Here, N denotes the maximum size of a group (which is at most the number of nodes in the tree), K denotes the maximum requirement value of any group (which in turn is at most N ) and m denotes the number of groups. 6

3.5 Cost. Overall, the basic rounding step is per-

Definition 4.1. A set of metric spaces S over V is said to -probabilistically approximate a metric space M over V, if (1) for all x; y 2 V and S 2 S, dS (x; y) dM (x; y), and (2) there exists a probability distribution D over metric spaces in S such that for all x; y 2 V, E dD (x; y)] dM (x; y). Bartal 4, 5] proved the following theorem. Theorem 4.2. Every weighted connected graph G on n vertices can be -probabilistically approximated by a set of weighted trees, where= O(log n log log n). Moreover, the proba

bility distribution can be computed in polynomial time. The trees that we get from Bartal's algorithm are not subtrees of the original graph. Only their leaves are the original vertices of G. To solve the covering Steiner tree problem on a general graph G, rst nd a set of trees and the distribution on them that O(log n log log n)-approximates G. Then pick a tree from the distribution and solve the covering Steiner tree problem on it. Now this solution subtree must be transformed into a subgraph of G, and this can be done by simply taking the tour that visits all the leaves of the solution tree, as in the classical 2-approximation for the metric TSP. The distances in the tree are greater than those in the original graph, so this tour will at most double the cost of the solution tree. The expected cost of this tree is O(log n log log n log N log m log K ) times the optimum. By using Markov's inequality, we nally get the following theorem. Theorem 4.3. The algorithm described above with high probability nds a covering Steiner tree of cost O(log n log log n log N log m log K ) times the cost of the optimal tree.

4 Extensions 4.1 General metrics.

4.2 Improved metric approximations. The fol-

lowing improvement of Bartal's result to graphs that exclude small minors is presented by Konjevod et al 15]. Theorem 4.4. Let G be an n-node graph that excludes Ks;s as a minor. Then G can be -probabilistically approximated by a set of weighted trees, where= O(s3 log n). Moreover, the probability distribution can be computed in polynomial time. This improved result (for constant s) applies, e.g., to planar graphs, which exclude K3;3 as a minor. This theorem, together with the arguments from the previous section, then gives an improved approximation ratio of O(log n log N log m log K ) for such graphs.

The covering Steiner tree problem is a common generalization of the k-MST and the group Steiner problems: Given an edge weighted graph, with subsets of vertices called the groups, and a requirement for each group which is an integer of value at most the si

Since distances in the Euclidean plane can be approximated to within a factor of 2 by a planar graph 8], the improvements also apply to this case. More formally, if the edge lengths of the resulting planar graph can be assumed to be integers in a polynomial range, then we can probabilistically approximate the original distances by trees with only a logarithmic loss. Even if these assumptions cannot be made, by identifying some points we can assume the distances to be in f1;:::; O(n2 )g. This can be done so that the optimum value of a covering Steiner tree only changes by a factor of 1+ for any constant as in 1]. ize our main procedure by using ideas from 7] to obtain the same guarantees. We defer the details to a full version of the paper.

4.3 Derandomization. It is possible to derandom-

Acknowledgements. Thanks to Naveen Garg, Madhav Marathe and Neal Young for helpful conversations. References1] S. Arora. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, pages 2{11, 1996. 2] S. Arora and G. Karakostas. A 2+ approximation algorithm f

or the k-mst problem. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, 2000. 3] S. Arya and H. Ramesh. A 2.5-factor approximation algorithm for the k-mst problem. Information Processing Letters, 65:117{118, 1998. 4] Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, pages 184{193, October 1996. 5] Y. Bartal. On approximating arbitrary metrics by tree metrics. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 161{168, 1998. 6] A. Blum, R. Ravi, and S. Vempala. A constant-factor approximation for the k-mst problem. In Proceedings of the 28thAnnual ACM Symposium on Theory of Computing, pages 442{448, 1996. 7] M. Charikar, C. Chekuri, A. Goel, and S. Guha. Rounding via trees: deterministic approximation algorithms for group steiner trees and k-median. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 114{123, 1998. 8] L. P. Chew. There are planar graphs almost as good as the complete graph. Journal of Computer and System Sciences, 39(2):205{219, Oct. 1989.

9] M. Fischetti, H. W. Hamacher, K. J rnsten, and F. Ma oli. Weighted k-cardinality trees: complexity and polyhedral structure. Networks, 24:11{21, 1994. 10] N. Garg. A 3-approximation for the minimum tree spanning k vertices. In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, pages 302{309, Oct. 1996. 11] N. Garg. Personal communication, September 1999. 12] N. Garg, G. Konjevod, and R. Ravi. A polylogarithmic approximation algorithm for the group Steiner tree problem. In Proceedings of the 9th Annual ACMSIAM Symposium on Discrete Algorithms, pages 253{ 259, 1998. 13] S. Janson. Poisson approximations for large deviations. Randoms Structures and Applications, 1:221{ 230, 1990. 14] P. N. Klein and R. Ravi. A nearly best-possible approximation algorithm for node-weighted Steiner tree. J. Algorithms, 19:104{115, 1995. 15] G. Konjevod, R. Ravi, and F. S. Salman. On approximating planar metrics by tree metrics. manuscript, Jul. 1997. 16] R. Ravi, R. Sundaram, M. V. Marathe, D. Rosenkrantz, and S. S. Ravi. Spanning trees|short or small. SIAM J. Discrete Math., 9:178{200, 1996. 17] G. Reich and P. Widmayer. Beyond Steiner's problem: A VLSI oriented generalization. In Graph-Theoretic Concepts in Computer Science WG89, volume 411 of Lecture Notes in Computer Science, pages 196{210. Springer, 1990.

本文来源：https://www.bwwdw.com/article/l62q.html