Volume 2 (2006) Article 3 pp. 53-64
An Improved Approximation Ratio for the Covering Steiner Problem
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.