A better approximation algorithm for the budget prize collecting tree problem

A better approximation algorithm for the budget prize collecting tree problem

0.00 Avg rating—0 Votes
Article ID: iaor20051036
Country: Netherlands
Volume: 32
Issue: 4
Start Page Number: 316
End Page Number: 319
Publication Date: Jul 2004
Journal: Operations Research Letters
Authors:
Keywords: combinatorial analysis, heuristics
Abstract:

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 find a subtree T′(V′,E′) that maximizes Σv∈V′ p(v), subject to Σe∈E′ c(e)⩽B. We present a (4+ϵ)-approximation algorithm.

Reviews

Required fields are marked *. Your email address will not be published.