file.pdf (292.62 kB)

Download file# Stochastic Steiner Tree with Non-Uniform Inflation

journal contribution

posted on 01.12.2013, 00:00 by Anupam Gupta, MohammadTaghi Hajiaghayi, Amit KumarWe 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 E M 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 $\widehat{\pi}$ (the so-called “stochastic MST case”)