- On complexity of Shmoys - Swamy class of two-stage linear stochastic programming problems Arkadi Nemirovski (nemirovsisye.gatech.edu) Alexander Shapiro (ashapiroisye.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/2006Entry Accepted: 07/28/2006Entry Last Modified: 07/28/2006Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.