𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP

✍ Scribed by Archer, Aaron; Bateni, MohammadHossein; Hajiaghayi, MohammadTaghi; Karloff, Howard

Book ID
118161211
Publisher
Society for Industrial and Applied Mathematics
Year
2011
Tongue
English
Weight
317 KB
Volume
40
Category
Article
ISSN
0097-5397

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