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.
Citation
Preprint, School of Industrial and Systems Engineering, Georgia Institute of Technology
Article
View On complexity of Shmoys - Swamy class of two-stage linear stochastic programming problems