𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the approximability of Dense Steiner Problems

✍ Scribed by Hauptmann, Mathias

Book ID
120515790
Publisher
Elsevier Science
Year
2013
Tongue
English
Weight
260 KB
Volume
21
Category
Article
ISSN
1570-8667

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the approximability of the Steiner tr
On the approximability of the Steiner tree problem
✍ Martin Thimm πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 165 KB

We show that it is not possible to approximate the minimum Steiner tree problem within 1 + 1 162 unless RP = NP. The currently best known lower bound is 1 + 1 400 . The reduction is from H astad's nonapproximability result for maximum satisΓΏability of linear equation modulo 2. The improvement on the

Differential approximation results for t
Differential approximation results for the Steiner tree problem
✍ M Demange; J Monnot; V.Th Paschos πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 654 KB

we study the approximability of three versions of the Steiner tree problem. For the first one where the input graph is only supposed connected, we show that it is not approximable within better than IV \ Nj-' for any E E (0, l), where V and N are the vertex-set of the input graph and the set of term

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