English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  A polylogarithmic approximation algorithm for group Steiner tree problem

Garg, N., Konjevod, G., & Ravi, R.(1997). A polylogarithmic approximation algorithm for group Steiner tree problem (MPI-I-97-1-027). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

Files

show Files
hide Files
:
MPI-I-97-1-027.pdf (Any fulltext), 227KB
Name:
MPI-I-97-1-027.pdf
Description:
-
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

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

Content

show
hide
Free keywords: -
 Abstract: The group Steiner tree problem is a generalization of the Steiner tree problem where we are given several subsets (groups) of vertices in a weighted graph, and the goal is to find a minimum-weight connected subgraph containing at least one vertex from each group. The problem was introduced by Reich and Widmayer and finds applications in VLSI design. The group Steiner tree problem generalizes the set covering problem, and is therefore at least as hard. We give a randomized $O(\log^3 n \log k)$-approximation algorithm for the group Steiner tree problem on an $n$-node graph, where $k$ is the number of groups.The best previous performance guarantee was $(1+\frac{\ln k}{2})\sqrt{k}$ (Bateman, Helvig, Robins and Zelikovsky). Noting that the group Steiner problem also models the network design problems with location-theoretic constraints studied by Marathe, Ravi and Sundaram, our results also improve their bicriteria approximation results. Similarly, we improve previous results by Slav{\'\i}k on a tour version, called the errand scheduling problem. We use the result of Bartal on probabilistic approximation of finite metric spaces by tree metrics to reduce the problem to one in a tree metric. To find a solution on a tree, we use a generalization of randomized rounding. Our approximation guarantees improve to $O(\log^2 n \log k)$ in the case of graphs that exclude small minors by using a better alternative to Bartal's result on probabilistic approximations of metrics induced by such graphs (Konjevod, Ravi and Salman) -- this improvement is valid for the group Steiner problem on planar graphs as well as on a set of points in the 2D-Euclidean case.

Details

show
hide
Language(s): eng - English
 Dates: 1997
 Publication Status: Published in print
 Pages: 7 p.
 Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
 Table of Contents: -
 Rev. Type: -
 Identifiers: Report Nr.: MPI-I-97-1-027
BibTex Citekey: GargKonjevodRavi97
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Research Report / Max-Planck-Institut für Informatik
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -