Prize-Collecting Bottleneck Steiner Tree Problem

• INSTANCE: Graph $G=(V,E)$ , edge costs $c: E \rightarrow \mathbb{R}^+$ , set of terminals $S\subseteq V$ , 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$ .
• COST FUNCTION: $\max ( \displaystyle\max_{e \in E_{T}}c(e), \displaystyle\max_{v \notin V_{T}}\pi(v) )$
• OBJECTIVE: Minimize.
• Approx.: Can be solved exactly in polynomial time [63].
• Comment: This entry covers the penalty-based variant of the Prize-Collecting Steiner Tree Problem. The quota-based Prize-Collecting Steiner Tree Problem, as well as the related Steiner Forest problems can also be solved in polynomial time [63].