Quota Steiner Tree Problem with Profit

• INSTANCE: Graph $G=(V,E)$ , a cost function $c : E \rightarrow {\mathbb{R}^+}$ , a revenue function $r : V \rightarrow {\mathbb{R}^+}$ , quota $Q$ .
• SOLUTION: A tree $T = (V_T, E_T)$ in $G$ such that $V_T \subseteq V$ , $E_T \subseteq E$ and $\sum_{v \in V_T}r(v) \geq Q$ .
• COST FUNCTION: ${\sum_{e \in E_T}} c(e)$ .
• OBJECTIVE: Minimize.
• Approx.: Approximable within approximation ratio 2.5 [71].
• Hardness: NP-hard to approximate within $96\slash 95$ [36].
• Comment: The lower bound follows from the fact the the Quota Steiner Tree Problem with Profit contains the Steiner Tree Problem as a special case.