Back to Search
Start Over
A comment on 'computational complexity of stochastic programming problems'.
- Source :
-
Mathematical Programming . Sep2016, Vol. 159 Issue 1/2, p557-569. 13p. - Publication Year :
- 2016
-
Abstract
- Although stochastic programming problems were always believed to be computationally challenging, this perception has only recently received a theoretical justification by the seminal work of Dyer and Stougie (Math Program A 106(3):423-432, 2006). Amongst others, that paper argues that linear two-stage stochastic programs with fixed recourse are #P-hard even if the random problem data is governed by independent uniform distributions. We show that Dyer and Stougie's proof is not correct, and we offer a correction which establishes the stronger result that even the approximate solution of such problems is #P-hard for a sufficiently high accuracy. We also provide new results which indicate that linear two-stage stochastic programs with random recourse seem even more challenging to solve. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00255610
- Volume :
- 159
- Issue :
- 1/2
- Database :
- Academic Search Index
- Journal :
- Mathematical Programming
- Publication Type :
- Academic Journal
- Accession number :
- 117379746
- Full Text :
- https://doi.org/10.1007/s10107-015-0958-2