✦ LIBER ✦

Approximation algorithm for the group Steiner network problem

✍ Scribed by Michal Penn; Stas Rozenfeld

Publisher: John Wiley and Sons
Year: 2007
Tongue: English
Weight: 143 KB
Volume: 49
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.20151

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this article we study the group Steiner network problem, which is defined in the following way. Given a graph G = (V,E), a partition of its vertices into K groups and connectivity requirements between the different groups, the aim is to find simultaneously a set of representatives, one for each group, and a minimum cost connected subgraph that satisfies the connectivity requirements between the groups (representatives). This problem is a generalization of the Steiner network problem and the group Steiner tree problem, two known NP‐complete problems. We present an approximation algorithm for a special case of the group Steiner network problem with an approximation ratio of min {2(1 + 2__x__),2__I__}, where I is the cardinality of the largest group and x is a parameter that depends on the cost function. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(2), 160–167 2007

📜 SIMILAR VOLUMES

A Polylogarithmic Approximation Algorith

A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem

✍ Naveen Garg; Goran Konjevod; R. Ravi 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 130 KB

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 a

Approximation Algorithms for Directed St

Approximation Algorithms for Directed Steiner Problems

✍ Moses Charikar; Chandra Chekuri; To-yat Cheung; Zuo Dai; Ashish Goel; Sudipto Gu 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 181 KB

We give the first non-trivial approximation algorithms for the Steiner tree problem and the generalized Steiner network problem on general directed graphs. These problems have several applications in network design and multicast routing.

An improved approximation scheme for the

An improved approximation scheme for the Group Steiner Problem

✍ C. S. Helvig; Gabriel Robins; Alexander Zelikovsky 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 322 KB 👁 1 views

the Group Steiner Problem asks for a minimumcost tree which contains at least one node from each group N i N i N i . In this paper, we give polynomial-time O O O(k k k )approximation algorithms for any fixed > > > 0. This result improves the previously known O O O(k k k)-approximation. We also apply

Approximation Algorithms for Network Des

Approximation Algorithms for Network Design Problems on Bounded Subsets

✍ Dorit S. Hochbaum; Joseph (Seffi) Naor 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 141 KB

We address the problem of designing a network so that certain connectivity requirements are satisfied, at minimum cost of the edges used. The requirements are specified for each subset of vertices in terms of the number of edges with one endpoint in the set. We address a class of such problems, wher

Approximation algorithms for channel all

Approximation algorithms for channel allocation problems in broadcast networks

✍ Rajiv Gandhi; Samir Khuller; Aravind Srinivasan; Nan Wang 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 211 KB

Approximation Algorithms for Steiner and

Approximation Algorithms for Steiner and Directed Multicuts

✍ Philip N Klein; Serge A Plotkin; Satish Rao; Éva Tardos 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 277 KB

In this paper we consider the Steiner multicut problem. This is a generalization of the minimum multicut problem where instead of separating node pairs, the goal is to find a minimum weight set of edges that separates all given sets of nodes. A set is considered separated if it is not contained in a