Approximation algorithm for the group Steiner network problem

In this article we study the group Steiner network problem, which is defined in the following way. Given a graph G = ( V,E ), a partition of its vertices into K groups and connectivity requirements between the different groups, the aim is to find simultaneously a set of representatives, one for each group, and a minimum cost connected subgraph that satisfies the connectivity requirements between the groups (representatives). This problem is a generalization of the Steiner network problem and the group Steiner tree problem, two known NP‐complete problems. We present an approximation algorithm for a special case of the group Steiner network problem with an approximation ratio of min {2(1 + 2 x ),2 I }, where I is the cardinality of the largest group and x is a parameter that depends on the cost function. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(2), 160–167 2007