𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Elementary approximation algorithms for prize collecting Steiner tree problems

✍ Scribed by Shai Gutner

Book ID
108154547
Publisher
Elsevier Science
Year
2008
Tongue
English
Weight
194 KB
Volume
107
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A better approximation algorithm for the
A better approximation algorithm for the budget prize collecting tree problem
✍ Asaf Levin πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 206 KB

Given an undirected graph G = (V; E), an edge cost c(e) ¿ 0 for each edge e ∈ E, a vertex prize p(v) ¿ 0 for each vertex v ∈ V , and an edge budget B. The BUDGET PRIZE COLLECTING TREE PROBLEM is to ÿnd a subtree T = (V ; E ) that maximizes v∈V p(v), subject to e∈E c(e) 6 B. We present a (4 + )-appro

Variations of the prize-collecting Stein
Variations of the prize-collecting Steiner tree problem
✍ Olena Chapovska; Abraham P. Punnen πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 136 KB

## Abstract The prize‐collecting Steiner tree problem is well known to be NP‐hard. We consider seven variations of this problem generalizing several well‐studied bottleneck and minsum problems with feasible solutions as trees of a graph. Four of these problems are shown to be solvable in __O__(__m_

Approximation Algorithms for Directed St
Approximation Algorithms for Directed Steiner Problems
✍ Moses Charikar; Chandra Chekuri; To-yat Cheung; Zuo Dai; Ashish Goel; Sudipto Gu πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 181 KB

We give the first non-trivial approximation algorithms for the Steiner tree problem and the generalized Steiner network problem on general directed graphs. These problems have several applications in network design and multicast routing.