Fractional 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}^+$ , fixed cost $c_0 \geq 0$
• SOLUTION: A tree $T = (V_T, E_T)$ in $G$ such that $V_T \subseteq V$ , $E_T \subseteq E$ .
• COST FUNCTION: $\frac{\displaystyle\sum_{v \in V_T} r(v)}{c_0 + {\displaystyle\sum_{e \in E_T}} c(e)}$ .
• OBJECTIVE: Maximize.
• Hardness: NP-hard [39].