LP rounding approximation algorithms for stochastic network design

Anupam Gupta, R. Ravi, Amitabh Sinha

Research output: Contribution to journalArticlepeer-review


We study the Steiner tree problem and the single-cable single-sink network design problem under a two-stage stochastic model with recourse and finitely many scenarios. In these models, some edges are purchased in a first stage when only probabilistic information about the second stage is available. In the second stage, one of a finite number of specified scenarios is realized, which results in the set of terminals becoming known and the opportunity to purchase additional edges (under an inflated cost function) to augment the first-stage solution. We provide constant factor approximation algorithms for these problems by rounding the linear relaxation of IP formulations of the problems. Our algorithms involve solving the linear relaxation first, followed by a primal-dual routine that is guided by the LP solution. We also show that because our bounds are local (the cost of each component is bounded by its cost in the LP solution), we are able to obtain bounds that guard against a form of downside risk.

Original languageEnglish (US)
Pages (from-to)345-364
Number of pages20
JournalMathematics of Operations Research
Issue number2
StatePublished - May 2007


  • Approximation algorithm
  • LP rounding
  • Network design
  • Primal-dual method
  • Steiner tree
  • Stochastic optimization

ASJC Scopus subject areas

  • General Mathematics
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'LP rounding approximation algorithms for stochastic network design'. Together they form a unique fingerprint.

Cite this