An approximation algorithm for the covering Steiner problem
Goran Konjevod, R. Ravi · 2000
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 find 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 finding 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 ...