An Approximation Scheme For The Group Steiner Tree Problem

We address a practical problem which arises in several areas, including network design and VLSI circuit layout. Given an undirected weighted graph G = (V, E) and a family N = {N1, . . . ,N;.} of k disjoint groups of nodes N; Q V, the Group Steiner Problem asks for a minimum-cost tree which contains at least one node from each group Ng. In this paper, we give polynomial-time 0(k‘)- approximation algorithms for any fixed 5 > 0. This result improves the previously known 0(k)- approximation. We also apply our approximation algorithms to the Steiner problem in directed graphs, while guaranteeing the same performance ratio.
Note: Abstract extracted from PDF file via OCR

Helvig, CS, G Robins, and A Zelikovsky. "An Approximation Scheme For The Group Steiner Tree Problem." University of Virginia Dept. of Computer Science Tech Report (1997).