A Polylogarithmic Approximation Algorithm for the Group Steiner P.pdf.pdf' (372.44 kB)

A Polylogarithmic Approximation Algorithm for the Group Steiner Problem

Download (372.44 kB)
journal contribution
posted on 01.06.2005 by Naveen Garg, Goran Konjevod, Ramamoorthi Ravi
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.

History

Publisher Statement

All Rights Reserved

Date

01/06/2005

Exports