A Polylogarithmic Approximation Algorithm for the Group Steiner P.pdf.pdf' (372.44 kB)
A Polylogarithmic Approximation Algorithm for the Group Steiner Problem
journal contribution
posted on 2005-06-01, 00:00 authored by Naveen Garg, Goran Konjevod, Ramamoorthi RaviRamamoorthi RaviGiven 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.