Premium
An improved approximation scheme for the Group Steiner Problem
Author(s) -
Helvig C. S.,
Robins Gabriel,
Zelikovsky Alexander
Publication year - 2001
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200101)37:1<8::aid-net2>3.0.co;2-r
Subject(s) - steiner tree problem , group (periodic table) , scheme (mathematics) , mathematics , combinatorics , mathematical optimization , computer science , discrete mathematics , physics , mathematical analysis , quantum mechanics
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 = [ N 1 , …, N k ] of k disjoint groups of nodes N i ⊆ V , the Group Steiner Problem asks for a minimum‐cost tree which contains at least one node from each group N i . 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.