  


On complexity of Shmoys  Swamy class of twostage linear stochastic programming problems
Arkadi Nemirovski (nemirovsisye.gatech.edu) Abstract: We consider a class of twostage 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, twostage 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 Modify/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  