Shallow-Light $k$ -Steiner Tree

• INSTANCE: Graph $G=(V,E)$ , a set of terminals $S\subseteq V$ ,a buy cost function $b: E \rightarrow\mathbb{R}^+$ , a distance cost $r: E \rightarrow\mathbb{R}^+$ , cost bound $B$ and length bound $D$ .
• SOLUTION: A tree $T=(V_{T}, E_{T})$ in G such that $S \subseteq V_{T} \subseteq V$ , $E_{T} \subseteq E$ , $s \in V_{T}$ , $\vert S \cap V_{T}\vert \geq k$ , such that the diameter under $r$ -cost is at most $D$ and buy cost is at most $B$ .
• COST FUNCTION: $\sum_{e\in E_T}b(e)$
• OBJECTIVE: Minimize.
• Approx.: Admits an $(O(\log^{2}n), O(\log^{4}n))$ -approximation algorithm [58].
• Hardness: NP-hard to approximate within $c\cdot\log (n)$ for some constant $c$ [58].