✦ LIBER ✦

On the approximability of the Steiner tree problem

✍ Scribed by Martin Thimm

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 165 KB
Volume: 295
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(02)00414-0

No coin nor oath required. For personal study only.

✦ Synopsis

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 nonapproximability ratio is mainly based on the fact that our reduction does not use variable gadgets. This idea was introduced by Papadimitriou and Vempala.

📜 SIMILAR VOLUMES

The Steiner tree problem

✍ Dirk van Oudheusden 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 87 KB

On the terminal Steiner tree problem

✍ Guohui Lin; Guoliang Xue 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 69 KB

We investigate a practical variant of the well-known graph Steiner tree problem. In this variant, every target vertex is required to be a leaf vertex in the solution Steiner tree. We present hardness results for this variant as well as a polynomial time approximation algorithm with performance ratio

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

The 1-steiner tree problem

✍ George Georgakopoulos; Christos H Papadimitriou 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 480 KB

The full Steiner tree problem

✍ Chin Lung Lu; Chuan Yi Tang; Richard Chia-Tung Lee 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 358 KB

Motivated by the reconstruction of phylogenetic tree in biology, we study the full Steiner tree problem in this paper. Given a complete graph G = (V; E) with a length function on E and a proper subset R ⊂ V , the problem is to ÿnd a full Steiner tree of minimum length in G, which is a kind of Steine

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