✦ LIBER ✦

A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3

✍ Scribed by Hans Jürgen Prömel; Angelika Steger

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 100 KB
Volume: 36
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2000.1086

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we present an RNC approximation algorithm for the Steiner tree problem in graphs with performance ratio 5r3 and RNC approximation algorithms for the Steiner tree problem in networks with performance ratio 5r3 q ⑀ for all ⑀ ) 0. This is achieved by considering a related problem, the minimum spanning tree problem in weighted 3-uniform hypergraphs. For that problem we give a fully polynomial randomized approximation scheme. Our approach also gives rise to Ž . conceptually much easier and faster though randomized sequential approximation algorithms for the Steiner tree problem than the currently best known algorithms from Karpinski and Zelikovsky which almost match their approximation factor.

📜 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