A comment on computational complexity of stochastic programming problems
成果类型：
Article
署名作者：
Hanasusanto, Grani A.; Kuhn, Daniel; Wiesemann, Wolfram
署名单位：
Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Imperial College London
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-015-0958-2
发表日期：
2016
页码：
557-569
关键词：
摘要：
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.