Stochastic Steiner Forest

• INSTANCE: A graph $G=(V,E)$ , an edge cost function $c : E \rightarrow {\mathbb{R}}_+$ , a probability distribution $\pi$ over sets of source-sink pairs $2^{\binom{V}{2}}$ , and an $inflation$ parameter $\lambda \geq 1$ .

• SOLUTION: A set of first-stage edges $E_0$ and for each $D \in 2^{\binom{V}{2}}$ , a set of second-stage edges $E_D$ such that (i) the edges in $E_0 \bigcup E_D$ connect each of the pairs in D.
• COST FUNCTION: $\sum_{e \in E_0} c_e + \mathbb{E}_{D \leftarrow \pi} [\sum_{e \in E_0} c_e]$ .
• OBJECTIVE: Minimize.
• Approx.: Approximable within 5 [55][49].

• Hardness: NP hard.

• Comment: A basic building block is an $s$ -star consisting of a non-terminal $c$ , called the center, $s$ terminals $t_1, . . . , t_s$ and edges $(c, t_1), . . . , (c, t_s)$ .