A Comment on “Computational Complexity of Stochastic Programming Problems”

Grani A. Hanasusanto (grani.hanasusantoepfl.ch)
Daniel Kuhn (daniel.kuhnepfl.ch)
Wolfram Wiesemann (wwimperial.ac.uk)

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 (Mathematical Programming 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 prove that the approximate solution of linear two-stage stochastic programs with random recourse is strongly #P-hard.

Keywords: stochastic programming; complexity theory

Category 1: Stochastic Programming

Citation:

Download: [PDF]

Entry Submitted: 03/16/2015
Entry Accepted: 03/16/2015
Entry Last Modified: 10/12/2015

Modify/Update this entry