English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Approximation algorithm for the group Steiner tree problem

Garg, N., Konjevod, G., & Ravi, R. (2000). Approximation algorithm for the group Steiner tree problem. Journal of Algorithms, 37(1), 66-84.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Garg, Naveen1, Author           
Konjevod, Goran, Author
Ravi, R., Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: 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

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-022000
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 518156
Other: Local-ID: C1256428004B93B8-0617D093C1C8F270C1256A0F005136B3-GargKonjevodRavi2000
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Journal of Algorithms
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 37 (1) Sequence Number: - Start / End Page: 66 - 84 Identifier: ISSN: 0196-6774