Prize-Collecting Steiner Forest

• INSTANCE: Graph $G=(V,E)$ , set of terminal pairs $S= \{ (s_{i},t_{i})\}_{1 \leq i \leq k}$ , cost function $c : E \rightarrow {\mathbb{R}}_+$ , penalty function $\pi : S \rightarrow {\mathbb{R}}_+$ .

• SOLUTION: A pair $(F,Q)$ , where $F$ is a forest and $Q\subseteq S$ contains all the terminal pairs that are not connected by $F$
• COST FUNCTION: $c(F)+ \pi (Q)$ .

• OBJECTIVE: Minimize.
• Approx.: Approximable within approximation ratio $3$ using a primal-dual approach. Approximable within approximation ratio $2.54$ by an LP-Rounding algorithm [100],[57].

• Hardness: NP-hard to approximate within 96/95 [36].

• Comment: PTAS exists for the special case when G is planar graph [29].