Polymatroid Steiner Problem

• INSTANCE: Graph $G=(V,E)$ , the edge weights $c: E \rightarrow \mathbb{R}^+$ , a polymatroid $P=P(V)$ .

• SOLUTION: A tree $T=(V_{T}, E_{T})$ in $G$ such that $S \subseteq V_{T} \subseteq V$ , $E_{T} \subseteq E$ and $T$ spans base of $P$ .
• COST FUNCTION: $\sum_{e \in E_T}c(e)$
• OBJECTIVE: Minimize.
• Approx.: Approximable within $O(\log^{3} k)$ [24], [27], [32].
• Hardness: NP-hard to approximate within $\log^{2\textbf{-}\epsilon}n$ for every $\epsilon >0$ [61], [24].
• Comment: The problem contains the Group Steiner Tree Problem as a special case [24].