# Stochastic steiner tree with non-uniform inflation

Anupam Gupta, Mohammad Taghi Hajiaghayi, Amit Kumar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

## Abstract

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 cM and cT (the costs for Monday and Tuesday, respectively). We are also given a probability distribution π : 2V → [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 ET(S) SO that the edges in EM ∪ ET(S) connect all the nodes in S. The goal is to minimize the cM(EM) + E S→π[ cT( ET(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 cT = σ × cM 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 4 n) approximation guarantee given by Chekuri et al. (FOCS 2006).

Original language English (US) Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings Springer Verlag 134-148 15 9783540742074 https://doi.org/10.1007/978-3-540-74208-1_10 Published - 2007 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007 - Princeton, NJ, United StatesDuration: Aug 20 2007 → Aug 22 2007

### Publication series

Name Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4627 LNCS 0302-9743 1611-3349

### Other

Other 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007 United States Princeton, NJ 8/20/07 → 8/22/07

## ASJC Scopus subject areas

• Theoretical Computer Science
• General Computer Science

## Fingerprint

Dive into the research topics of 'Stochastic steiner tree with non-uniform inflation'. Together they form a unique fingerprint.