This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Gupta, A. Articles by Sinha, A. Search for Related Content

LP Rounding Approximation Algorithms for Stochastic Network Design

Department of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Ross School of Business, University of Michigan, Ann Arbor, Michigan 48109
anupamg{at}cs.cmu.edu, http://www.cs.cmu.edu/anupamg
ravi{at}cmu.edu, http://www.tepper.cmu.edu/andrew/ravi
amitabh{at}umich.edu, http://www.umich.edu/amitabh

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.

Key Words: stochastic optimization; approximation algorithm; Steiner tree; network design; LP rounding; primal-dual method
History: Received: October 8, 2004; revision received: May 23, 2006;

This article has been cited by other articles:

				A. M.-C. So, J. Zhang, and Y. Ye Stochastic Combinatorial Optimization with Controllable Risk Aversion Level Mathematics of Operations Research, August 1, 2009; 34(3): 522 - 537. [Abstract] [PDF]