Stochastic Steiner Tree Problem

• INSTANCE: Graph $G=(V,E)$ , the root $r$ , first stage edge costs $c_{e} \geq 0, e \in E$ , inflation parameter $\sigma$ and probability distribution $\pi$ on the set of scenarios $K$ , where a scenario $k$ is a set of terminal nodes.
• SOLUTION: A subset of edges $E_{0} \subseteq E$ to be purchased in the first stage
• COST FUNCTION: $\sum_{e \in E_{0}} c_{e} + \mathbb{E}[\sum_{e \in E_k}c_{e}\sigma]$ while $E_{o} \cup E_{k}$ spans $S_{k}$ for every $k \in K$ , where $E_{k}$ is the set of edges that have to be bought in the second stage to connect all terminal nodes.
• OBJECTIVE: Minimize.
• Approx.: Approximable within 3.39 [101], [56].
• Hardness: NP-hard.
• Comment: In this model there are two separate stages: First stage, where $G, r, c_{e}, \sigma$ and $\pi$ are known. In this stage one must purchase set of edges $E_{0}$ that is predicted to be useful for connecting unknown set of vertices $k$ that will be drawn from $K$ according to $\pi$ . Second stage, where $k$ is revealed, cost of every edge increases by a factor of $\sigma$ and a set of edges $E_{k}$ has to be bought to connect all terminals. [49], [18].