Buy-at-Bulk k-Steiner Tree

• INSTANCE: Graph $G(V,E)$ , set of terminals $S\subseteq V$ , root $s\in S$ , an integer $k \leq \vert S\vert$ , a buy cost function $b: E \rightarrow\mathbb{R}^+$ , a distance cost $dist: E \rightarrow\mathbb{R}^+$ .
• 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$ .
• COST FUNCTION: $\sum_{e \in T }b(e)+\sum_{T \in S-s }dist(t,s)$ .
• OBJECTIVE: Minimize.
• Approx.: Approximable within approximation ratio $O(\log^{4}n)$ [58].
• Hardness: NP- hard to approximate within $c\cdot\log (n)$ for some constant $c$ [58] .