Theory of Computing
-------------------
Title : An Improved Approximation Ratio for the Covering Steiner Problem
Authors : Anupam Gupta and Aravind Srinivasan
Volume : 2
Number : 3
Pages : 53-64
URL : http://www.theoryofcomputing.org/articles/v002a003
Abstract
--------
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.
While many covering problems (e.g., the covering integer programs
such as set cover) become easier to approximate as the requirements
increase, the Covering Steiner problem remains at least as hard to
approximate as the Group Steiner problem; in fact, the best guarantees
previously known for the Covering Steiner problem were worse than
those for Group Steiner as the requirements became large. In this
work, we present an improved approximation algorithm whose guarantee
equals the best known guarantee for the Group Steiner problem.