Carnegie Mellon University
Browse
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 2005-06-01, 00:00 authored by Naveen Garg, Goran Konjevod, Ramamoorthi RaviRamamoorthi 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

2005-06-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC