# MPI-I-97-1-027

## 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

tree,

we use a generalization of randomized rounding. Our approximation

guarantees

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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 147 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: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1997-1-027

**BibTeX**
`@TECHREPORT{``GargKonjevodRavi97``,`

` 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},`

`}`