Polymatroid Directed 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$ , connecting a given root $r \in V$ to all vertices of a least one base of P.
• COST FUNCTION: $\sum_{e \in E_{T}}c(e)$ .
• OBJECTIVE: Minimize.
• Approx.: Approximable within $O(k^{\epsilon})$ for any $\epsilon >0$ ,
  approximable within $O(n^{c \lg n})$ in quasi-polynomial time[24], [27].
• Hardness: NP-hard to approximate within $\log^{2\textbf{-}\epsilon}n$ for every $\epsilon >0$ [61], [24]
• Comment: The problem contains the Directed Steiner Tree Problem as a special case [24].