A Polylogarithmic Approximation Algorithm for the Group Steiner Problem
journal contributionposted on 01.06.2005 by Naveen Garg, Goran Konjevod, Ramamoorthi Ravi
Any type of content formally published in an academic journal, usually following a peer-review process.
Given a weighted graph with some subsets of vertices called groups, the group Steiner tree problem is to find 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(i2k1/i) in time O(nik2i) (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.