Optimization Online


A Comment on “Computational Complexity of Stochastic Programming Problems”

Grani A. Hanasusanto (grani.hanasusanto***at***epfl.ch)
Daniel Kuhn (daniel.kuhn***at***epfl.ch)
Wolfram Wiesemann (ww***at***imperial.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


Download: [PDF]

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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society