Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


A polylogarithmic approximation algorithm for group Steiner tree problem

Garg, Naveen and Konjevod, Goran and Ravi, R.

MPI-I-97-1-027. November 1997, 7 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
The group Steiner tree problem is a generalization of the
Steiner tree problem where we are given several subsets (groups) of
vertices in
a weighted graph,
and the goal is to find a minimum-weight connected subgraph containing
at least one vertex from each group. The problem was introduced by
Reich and Widmayer and finds applications in VLSI design.
The group Steiner tree problem generalizes the set covering
problem, and is therefore at least as hard.

We give a randomized $O(\log^3 n \log k)$-approximation
algorithm for the group Steiner tree problem on an $n$-node graph, where

$k$ is the number of groups.The best previous performance guarantee was
$(1+\frac{\ln k}{2})\sqrt{k}$ (Bateman, Helvig, Robins and Zelikovsky).

Noting that the group Steiner problem also models the
network design problems with location-theoretic constraints studied by
Marathe, Ravi and Sundaram, our results also improve their bicriteria
approximation results. Similarly, we improve previous results by
Slav{\'\i}k on a tour version, called the errand scheduling problem.

We use the result of Bartal on probabilistic approximation of finite
metric spaces by tree metrics
to reduce the problem to one in a tree metric. To find a solution on a
we use a generalization of randomized rounding. Our approximation
improve to $O(\log^2 n \log k)$ in the case of graphs that exclude
small minors by using a better alternative to Bartal's result on
probabilistic approximations of metrics induced by such graphs
(Konjevod, Ravi and Salman) -- this improvement is valid for the group
Steiner problem on planar graphs as well as on a set of points in the
2D-Euclidean case.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-97-1-027.ps147 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView

URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Garg, Naveen and Konjevod, Goran and Ravi, R.},
  TITLE = {A polylogarithmic approximation algorithm for group Steiner tree problem},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-97-1-027},
  MONTH = {November},
  YEAR = {1997},
  ISSN = {0946-011X},