A constant-factor approximation for stochastic steiner forest

Anupam Gupta, Amit Kumar

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

Abstract

We consider the stochastic Steiner forest problem: suppose we were given a collection of Steiner forest instances, and were guaranteed that a random one of these instances would appear tomorrow; moreover, the cost of edges tomorrow will be λ times the cost of edges today. Which edges should we buy today so that we can extend it to a solution for the instance arriving tomorrow, to minimize the expected total cost? While very general results have been developed for many problems in stochastic discrete optimization over the past years, the approximation status of the stochastic Steiner Forest problem has remained open, with previous works yielding constant-factor approximations only for special cases. We resolve the status of this problem by giving a constant-factor primal-dual based approximation algorithm.

Original languageEnglish (US)
Title of host publicationSTOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing
Pages659-668
Number of pages10
DOIs
StatePublished - 2009
Event41st Annual ACM Symposium on Theory of Computing, STOC '09 - Bethesda, MD, United States
Duration: May 31 2009Jun 2 2009

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other41st Annual ACM Symposium on Theory of Computing, STOC '09
Country/TerritoryUnited States
CityBethesda, MD
Period5/31/096/2/09

Keywords

  • Approximation algorithms
  • Stochastic algorithms

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'A constant-factor approximation for stochastic steiner forest'. Together they form a unique fingerprint.

Cite this