A polylogarithmic approximation algorithm for the group Steiner tree problem

Given a weighted graph with some subsets of vertices called groups, the group Steiner tree problem is to nd a minimum-weight subgraph which contains at least one vertex from each group. We give a randomized algorithm with a polylogarithmic approximation guarantee for the group Steiner tree problem. The previous best approximation guarantee was O(i 2 k 1=i ) in time O(n i k 2i ) (Charikar, Chekuri, Goel and Guha). Our algorithm also improves existing approximation results for network design problems with location-based constraints and for the symmetric generalized traveling salesman problem. Key Words: Steiner tree, approximation algorithms, set cover, randomized rounding, network design, tree decompositions 1 Introduction. 1.1 Motivation. The group Steiner problem was introduced by Reich and Widmayer [27]. The problem arises in wire routing with multi-port terminals in physical VLSI design. The traditional model assuming single ports for each of the terminals to be c...