Resumen
Given an undirected graph G=(V,E), an edge cost c(e)0 for each edge eE, a vertex prize p(v)0 for each vertex vV, and an edge budget B. The is to find a subtree T′=(V′,E′) that maximizes ∑vV′ p(v), subject to ∑eE′ c(e)B. We present a (4+)-approximation algorithm.
