An approximation algorithm for the group Steiner problem

ABSTRACT

The input in the Group-Steiner Problem consists of an undirected connected graph with a cost function p(e) over the edges and a collection of subsets of vertices {gi}. Each subset gi is called a group and the vertices in ∪ gi are called terminals. The goal is to find a minimum cost tree that contains at least one terminal from every group.We give the first combinatorial polylogarithmic ratio approximation for the problem on trees. Let m denote the number of groups and S denote the number of terminals. The approximation ratio of our algorithm is O(log S · log m/log log S) = O(log²n/log log n). This is an improvement by a Θ(log log n) factor over the previously best known approximation ratio for the Group Steiner Problem on trees [GKR98].Our result carries over to the Group Steiner Problem on general graphs and to the Covering Steiner Problem. Garg et al. [GKR98] presented a reduction of the Group Steiner Problem on general graphs to trees. Their reduction employs Bartal's [B98] approximation of graph metrics by tree metrics. Our algorithm on trees implies an approximation algorithm of ratio O(log S · log m · log n · log log n/log log S) = O(log³n) for the Group Steiner Problem on general graphs. The previously best known approximation ratio for this problem on general graphs, as a function of n, is O(log³n · log log n) [GKR98]. Our algorithm in conjunction with ideas of [EKS01] gives an O(log S · log m · log n · log log n/log log S) = O(log³n)-approximation ratio for the more general Covering Steiner Problem, improving the best known approximation ratio (as a function of n) for the Covering Steiner Problem by a Θ(log log n) factor.

REFERENCES

• 1: Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
• 2: {BHRZ97} C. D. Bateman and C. S. Helvig and G. Robins and A. Zelikovsky. Provably good routing tree construction with multi-port terminals. ISPD, 1997.
• 3: Moses Charikar , Chandra Chekuri, Approximation algorithms for directed Steiner problems, Journal of Algorithms, v.33 n.1, p.73-91, Oct. 1999 [doi>10.1006/jagm.1999.1042]
• 4: Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha , Serge Plotkin, Approximating a Finite Metric by a Small Number of Tree Metrics, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.379, November 08-11, 1998
• 5: {EKS01} G. Even and G. Kortsarz and W. Slany. On network design problems: fixed cost flow and the Covering Steiner Problem, manuscript, May 2001.
• 6: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 7: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 8: {GK99} S. Guha and S. Khuller. Approximating algorithms for connected dominating sets. Algorithmica, 20:374-387, 1999.
• 9: Naveen Garg , Goran Konjevod , R. Ravi, A polylogarithmic approximation algorithm for the Steiner group tree problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.253-259, January 25-27, 1998, San Francisco, California, United States
• 10: {J74} Johnson, D. S. Approximation algorithms for combinatorial problems, J. Comput. System Sci., 9, 256-278, 1974.
• 11: Goran Konjevod , R. Ravi, An approximation algorithm for the covering Steiner problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.338-344, January 09-11, 2000, San Francisco, California, United States
• 12: {KRS01} G. Konjevod, R. Ravi, and Aravind Srinivasan, Approximation Algorithms for the Covering Steiner Problem. Manuscript, 2001.
• 13: Guy Kortsarz , David Peleg, Approximating the weight of shallow Steiner trees, Discrete Applied Mathematics, v.93 n.2-3, p.265-285, July 20, 1999 [doi>10.1016/S0166-218X(99)00111-0]
• 14: Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258641]
• 15: G. Reich , P. Widmayer, Beyond Steiner's problem: a VLSI oriented generalization, Proceedings of the fifteenth international workshop on Graph-theoretic concepts in computer science, p.196-210, March 1990, Castle Rolduc, The Netherlands