Prize-Collecting k-Bottleneck Steiner Tree Problem

• INSTANCE: Graph $G=(V,E)$ , edge costs $c: E \rightarrow \mathbb{R}^+$ , set of terminals $S\subseteq V$ , positive integer $k$ , a penalty function $\pi:S \rightarrow \mathbb{R}^+\strut$ .
• SOLUTION: Tree $T=(V_{T}, E_{T})$ in $G$ such that $V_{T} \subseteq V$ , $E_{T} \subseteq E$ and $\vert V_{T}\setminus S\vert \leq k$ (at most k Steiner nodes used).
• COST FUNCTION: $\max ( \displaystyle\max_{e \in E_{T}}c(e), \displaystyle\max_{v \notin V_{T}}\pi(v) )$
• OBJECTIVE: Minimize.
• Hardness: NP-Hard to approximate within $2-\epsilon$ on undirected metric graphs [2].
• Approx.: Approximable within approximation ratio $2$ on undirected metric graphs [63].