## 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 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 ^{4} n) approximation guarantee given by Chekuri et al. (FOCS 2006).

Original language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization |

Subtitle of host publication | Algorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings |

Publisher | Springer Verlag |

Pages | 134-148 |

Number of pages | 15 |

ISBN (Print) | 9783540742074 |

DOIs | |

State | Published - 2007 |

Event | 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 States Duration: 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) |
---|---|

Volume | 4627 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 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 |
---|---|

Country/Territory | United States |

City | Princeton, NJ |

Period | 8/20/07 → 8/22/07 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science