Stochastic steiner tree with non-uniform inflation

We study the Steiner Tree problem in the model of two-stage stochastic optimization with non-uniform inflation factors, and give a poly-logarithmic approximation factor for this problem. In this problem, we are given a graph G = (V, E), with each edge having two costs c_M and c_T (the costs for Monday and Tuesday, respectively). We are also given a probability distribution π : 2^V → [0, 1] over subsets of V, and will be given a client set S drawn from this distribution on Tuesday. The algorithm has to buy a set of edges EM on Monday, and after the client set S is revealed on Tuesday, it has to buy a (possibly empty) set of edges E_T(S) SO that the edges in E_M ∪ E_T(S) connect all the nodes in S. The goal is to minimize the c_M(E_M) + E _S→π[ c_T( E_T(S))]. We give the first poly-logarithmic approximation algorithm for this problem. Our algorithm builds on the recent techniques developed by Chekuri et al. (FOCS 2006) for multi-commodity Cost-Distance. Previously, the problem had been studied for the cases when c_T = σ × c_M for some constant σ > 1 (i.e., the uniform case), or for the case when the goal was to find a tree spanning all the vertices but Tuesday's costs were drawn from a given distribution π̂ (the so-called "stochastic MST case"). We complement our results by showing that our problem is at least as hard as the single-sink Cost-Distance problem (which is known to be Ω(log log n) hard). Moreover, the requirement that Tuesday's costs are fixed seems essential: if we allow Tuesday's costs to dependent on the scenario as in stochastic MST, the problem becomes as hard as Label Cover (which is Ω(2 ^log1-∈)-hard). As an aside, we also give an LP-rounding algorithm for the multi-commodity CostDistance problem, matching the O(log ⁴ n) approximation guarantee given by Chekuri et al. (FOCS 2006).