Journal
MATHEMATICAL PROGRAMMING
Volume 159, Issue 1-2, Pages 557-569Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-015-0958-2
Keywords
Stochastic programming; Complexity theory; Two-stage problems
Categories
Funding
- Swiss National Science Foundation [BSCGI0_157733]
- EPSRC [EP/M028240/1, EP/M027856/1]
- Engineering and Physical Sciences Research Council [EP/I014640/1, EP/M027856/1, EP/M028240/1] Funding Source: researchfish
- EPSRC [EP/M028240/1, EP/I014640/1, EP/M027856/1] Funding Source: UKRI
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available