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/2006
Entry Accepted: 07/28/2006
Entry Last Modified: 07/28/2006

Modify/Update this entry