An improved approximation scheme for the Group Steiner Problem

Abstract

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, …, Nk] of k disjoint groups of nodes Ni ⊆ V, the Group Steiner Problem asks for a minimum-cost tree which contains at least one node from each group Ni. In this paper, we give polynomial-time O(kϵ-approximation algorithms for any fixed ϵ > 0. This result improves the previously known O(k)-approximation. We also apply our approximation algorithms to the Steiner problem in directed graphs, while guaranteeing the same performance ratio. © 2001 John Wiley & Sons, Inc.