𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximation Algorithms for Directed Steiner Problems

✍ Scribed by Moses Charikar; Chandra Chekuri; To-yat Cheung; Zuo Dai; Ashish Goel; Sudipto Guha; Ming Li

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
181 KB
Volume
33
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

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

Approximation algorithm for the group St
Approximation algorithm for the group Steiner network problem
✍ Michal Penn; Stas Rozenfeld πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 143 KB

## 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 repres

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

Combinatorial Approximation Algorithms f
Combinatorial Approximation Algorithms for Generalized Flow Problems
✍ Jeffrey D Oldham πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 226 KB

Generalized network flow problems generalize normal network flow problems by specifying a flow multiplier Β΅ v w for each arc v w . For every unit of flow entering the arc, Β΅ v w units of flow exit. We present a strongly polynomial algorithm for a single-source generalized shortest paths problem, usi