✦ LIBER ✦

Lower bounds for the relative greedy algorithm for approximating Steiner trees

✍ Scribed by Stefan Hougardy; Stefan Kirchner

Publisher: John Wiley and Sons
Year: 2006
Tongue: English
Weight: 125 KB
Volume: 47
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.20100

No coin nor oath required. For personal study only.

📜 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

Complexity Lower Bounds for Approximatio

Complexity Lower Bounds for Approximation Algebraic Computation Trees

✍ Felipe Cucker; Dima Grigoriev 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 159 KB

We prove lower bounds for approximate computations of piecewise polynomial functions which, in particular, apply for round-off computations of such functions.

A strong lower bound for the Node Weight

A strong lower bound for the Node Weighted Steiner Tree Problem

✍ Engevall, Stefan; G�the-Lundgren, Maud; V�rbrand, Peter 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 84 KB 👁 1 views

In this paper, we study the Node Weighted Steiner Tree Problem (NSP). This problem is a generalization of the Steiner tree problem in the sense that vertex weights are considered. Given an undirected graph, the problem is to find a tree that spans a subset of the vertices and is such that the total

A Nearly Best-Possible Approximation Alg

A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees

✍ P. Klein; R. Ravi 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 488 KB

The sequential sum problem and performan

The sequential sum problem and performance bounds on the greedy algorithm for the on-line Steiner problem

✍ Zevi Miller; Dan Pritikin; Manley Perkel; I.H. Sudborough 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 331 KB

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