A greedy approximation algorithm for the group Steiner problem

In the group Steiner problem we are given an edge-weighted graph G = (V, E, w) and in subsets of vertices {g(i)}(i=1)(m). Each subset gi is called a group and the vertices in boolean OR(i)g(i) are called terminals. It is required to find a minimum weight tree that contains at least one terminal from every group. We present a poly-logarithmic ratio approximation for this problem when the input graph is a tree. Our algorithm is a recursive greedy algorithm adapted from the greedy algorithm for the directed Steiner tree problem [Approximating the weight of shallow Steiner trees, Discrete Appl. Math. 93 (1999) 265-285, Approximation algorithms for directed Steiner problems, J. Algorithms 33 (1999) 73-91]. This is in contrast to earlier algorithms that are based on rounding a linear programming based relaxation for the problem [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259, On directed Steiner trees, Proceedings of SODA, 2002, pp. 59-63]. We answer in positive a question posed in [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259] on whether there exist good approximation algorithms for the group Steiner problem that are not based on rounding linear programs. For every fixed constant epsilon > 0, our algorithm gives an O((log Sigma(i)vertical bar g(i)vertical bar)(1+epsilon) center dot log m) approximation in polynomial time. Approximation algorithms for trees can be extended to arbitrary undirected graphs by probabilistically approximating the graph by a tree. This results in an additional multiplicative factor of O(log vertical bar V vertical bar) in the approximation ratio, where vertical bar V vertical bar is the number of vertices in the graph. The approximation ratio of our algorithm on trees is slightly worse than the ratio of O(log(max(i)vertical bar g(i)vertical bar) center dot log m) provided by the LP based approaches. (c) 2005 Elsevier B.V. All rights reserved.