A constant-factor approximation for stochastic steiner forest

Anupam Gupta; Amit Kumar

doi:10.1145/1536414.1536504

A constant-factor approximation for stochastic steiner forest

Anupam Gupta, Amit Kumar

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	STOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing
Pages	659-668
Number of pages	10
DOIs	https://doi.org/10.1145/1536414.1536504
State	Published - 2009
Event	41st Annual ACM Symposium on Theory of Computing, STOC '09 - Bethesda, MD, United States Duration: May 31 2009 → Jun 2 2009

Publication series

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

Other

Other	41st Annual ACM Symposium on Theory of Computing, STOC '09
Country/Territory	United States
City	Bethesda, MD
Period	5/31/09 → 6/2/09

Keywords

Approximation algorithms
Stochastic algorithms

ASJC Scopus subject areas

Software

Access to Document

10.1145/1536414.1536504

Cite this

Gupta, A & Kumar, A 2009, A constant-factor approximation for stochastic steiner forest. in STOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 659-668, 41st Annual ACM Symposium on Theory of Computing, STOC '09, Bethesda, MD, United States, 5/31/09. https://doi.org/10.1145/1536414.1536504

@inproceedings{8b9c57528a6a48e3bae14ff9c487827f,

title = "A constant-factor approximation for stochastic steiner forest",

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.",

keywords = "Approximation algorithms, Stochastic algorithms",

author = "Anupam Gupta and Amit Kumar",

year = "2009",

doi = "10.1145/1536414.1536504",

language = "English (US)",

isbn = "9781605585062",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

pages = "659--668",

booktitle = "STOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing",

note = "41st Annual ACM Symposium on Theory of Computing, STOC '09 ; Conference date: 31-05-2009 Through 02-06-2009",

}

TY - GEN

T1 - A constant-factor approximation for stochastic steiner forest

AU - Gupta, Anupam

AU - Kumar, Amit

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Stochastic algorithms

UR - http://www.scopus.com/inward/record.url?scp=71049117777&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=71049117777&partnerID=8YFLogxK

U2 - 10.1145/1536414.1536504

DO - 10.1145/1536414.1536504

M3 - Conference contribution

AN - SCOPUS:71049117777

SN - 9781605585062

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 659

EP - 668

BT - STOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing

T2 - 41st Annual ACM Symposium on Theory of Computing, STOC '09

Y2 - 31 May 2009 through 2 June 2009

ER -

A constant-factor approximation for stochastic steiner forest

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this