Optimization Online


On complexity of Shmoys - Swamy class of two-stage linear stochastic programming problems

Arkadi Nemirovski (nemirovs***at***isye.gatech.edu)
Alexander Shapiro (ashapiro***at***isye.gatech.edu)

Abstract: We consider a class of two-stage linear stochastic programming problems, introduced by Shmoys and Swamy (2004), motivated by a relaxation of a stochastic set cover problem. We show that the sample size required to solve this problem by the sample average approximation (SAA) method with a relative accuracy $\kappa>0$ and confidence $1-\alpha$ is polynomial in $\kappa$, $\log(\alpha^{-1})$, dimensions of the problem and a certain parameter $\lambda$. This implies that such problems can be solved in time polynomial in these parameters, the result obtained in Shmoys and Swamy (2004) by a different method.

Keywords: Set cover problem, computational complexity, two-stage stochastic programming

Category 1: Stochastic Programming

Category 2: Combinatorial Optimization (Approximation Algorithms )

Citation: Preprint, School of Industrial and Systems Engineering, Georgia Institute of Technology

Download: [PDF]

Entry Submitted: 07/28/2006
Entry Accepted: 07/28/2006
Entry Last Modified: 07/28/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society