120
IRUS TotalDownloads
Altmetric
A comment on "computational complexity of stochastic programming problems"
File | Description | Size | Format | |
---|---|---|---|---|
complexity.pdf | Accepted version | 313.03 kB | Adobe PDF | View/Open |
Title: | A comment on "computational complexity of stochastic programming problems" |
Authors: | Hanasusanto, GA Kuhn, D Wiesemann, W |
Item 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. |
Issue Date: | 22-Oct-2015 |
Date of Acceptance: | 6-Oct-2015 |
URI: | http://hdl.handle.net/10044/1/38437 |
DOI: | https://dx.doi.org/10.1007/s10107-015-0958-2 |
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/Funder: | Engineering & Physical Science Research Council (E |
Funder's Grant Number: | EP/M028240/1 |
Keywords: | 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 |
Appears in Collections: | Imperial College Business School |