Prize-Collecting Steiner Tree

• INSTANCE: Graph $G=(V,E)$ , cost function $c: E \rightarrow \mathbb{R}^+ \strut$ , set of terminals $S\subseteq V$ , a penalty function $\pi:S \rightarrow \mathbb{R}^+\strut$ .
• SOLUTION: A tree $T=(V_{T}, E_{T})$ in $G$ such that $V_{T} \subseteq V$ , $E_{T} \subseteq E$ .
• COST FUNCTION: $\sum_{e \in E_{T} } c(e)+\sum _{s \in S\backslash V_{T} } \pi (s)$ .
• OBJECTIVE: Minimize.
• Approx.: Approximable within $1.9672- \delta$ for some $\delta > 0$ [6].
• Hardness: NP-hard to approximate within 96/95 [36]. a PTAS for the special case when $G$ is a planar graph [29].