file.pdf (292.62 kB)
0/0

Stochastic Steiner Tree with Non-Uniform Inflation

Download (292.62 kB)
journal contribution
posted on 01.12.2013 by Anupam Gupta, MohammadTaghi Hajiaghayi, Amit Kumar
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 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”)

History

Publisher Statement

© 2013 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Date

01/12/2013

Exports

Exports