A comment on "computational complexity of stochastic programming problems"
File(s)
Accepted version
Author(s)
Hanasusanto, GA
Kuhn, D
Wiesemann, W
Type
Journal Article
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.
Date Issued
2015-10-22
Date Acceptance
2015-10-06
Citation
Mathematical Programming, 2015, 159 (1), pp.557-569
ISSN
0025-5610
Publisher
Springer Verlag
Start Page
557
End Page
569
Journal / Book Title
Mathematical Programming
Volume
159
Issue
1
Copyright Statement
© Springer Verlag 2015. The final publication is available at Springer via http://dx.doi.org/10.1007/s10107-015-0958-2
Sponsor
Engineering & Physical Science Research Council (E
Grant Number
EP/M028240/1
Subjects
Science & Technology
Technology
Physical Sciences
Computer Science, Software Engineering
Operations Research & Management Science
Mathematics, Applied
Computer Science
Mathematics
Stochastic programming
Complexity theory
Two-stage problems
Operations Research
0102 Applied Mathematics
0103 Numerical And Computational Mathematics
0802 Computation Theory And Mathematics
Publication Status
Published