A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem

✍ Scribed by Naveen Garg; Goran Konjevod; R. Ravi

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 130 KB
• Volume: 37
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2000.1096

✦ Synopsis

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 linds 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(log3 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 + ?)a (Bateman, Helvig, Robins and Zelikovsky).Noting that the group Steiner problem also models the network design problems with location-theoretic constraints studied by Marathe, Bavi and Sundaram, our results also improve their bicriteria approximation results. Similarly, we improve previous results by Slavik 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 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' nlog 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. -