𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximating Steiner trees in graphs with restricted weights

✍ Scribed by Halld�rsson, Magn�s M.; Ueno, Shuichi; Nakao, Hiroshi; Kajitani, Yoji

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
128 KB
Volume
31
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

We analyze the approximation ratio of the average distance heuristic for the Steiner tree problem on graphs and prove nearly tight bounds for the cases of complete graphs with binary weights {1, d} or weights in the interval [1, d], where d °2. The improvement over other analyzed algorithms is a factor of about e É 2.718.

📜 SIMILAR VOLUMES

Solving Steiner tree problems in graphs
Solving Steiner tree problems in graphs to optimality
✍ Koch, T.; Martin, A. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 261 KB 👁 2 views

In this paper, we present the implementation of a branch-and-cut algorithm for solving Steiner tree problems in graphs. Our algorithm is based on an integer programming formulation for directed graphs and comprises preprocessing, separation algorithms, and primal heuristics. We are able to solve nea

On finding a minimum spanning tree in a
On finding a minimum spanning tree in a network with random weights
✍ Colin McDiarmid; Theodore Johnson; Harold S. Stone 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 221 KB 👁 2 views

We investigate Prim's standard ''tree-growing'' method for finding a minimum spanning tree, when applied to a network in which all degrees are about d and the edges e Ž . have independent identically distributed random weights w e . We find that when the kth ' Ž . edge e is added to the current tree

The pilot method: A strategy for heurist
The pilot method: A strategy for heuristic repetition with application to the Steiner problem in graphs
✍ Duin, Cees; Vo�, Stefan 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB 👁 2 views

As a metaheuristic to obtain solutions of enhanced quality, we formulate the so-called pilot method. It is a tempered greedy method that is to avoid the greedy trap by looking ahead for each possible choice (memorizing the best result). Repeatedly, a so-called master solution is modified, each time