Budget Steiner Tree Problem with Profits

• INSTANCE: Graph $G=(V,E)$ , a cost function $c : E \rightarrow {\mathbb{R}^+}$ , a revenue function $r : V \rightarrow {\mathbb{R}^+}$ , budget $B$ .
• SOLUTION: A tree $T = (V_T, E_T)$ in $G$ such that $V_T \subseteq V$ , $E_T \subseteq E$ and $\sum_{e \in E_T}c(e) \leq B$ .
• COST FUNCTION: ${\sum_{v \in V_T}} r(v)$
• OBJECTIVE: Maximize.
• Approx.: Approximable within $(4 + \epsilon)$ for every $\epsilon >0$ [83]
• Hardness: NP-hard.