Volume 2 (2006)
Article 3 pp. 53-64
An Improved Approximation Ratio for the Covering Steiner Problem
Received: June 1, 2005
Published: February 17, 2006
Published: February 17, 2006
Keywords: algorithms, approximation algorithms, Steiner trees, randomized algorithms, network design
ACM Classification: C.2.0, F.2.2, G.1.6, G.3
AMS Classification: 68W20, 68W25, 90C59
Abstract: [Plain Text Version]
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.

Licensed under a Creative Commons License