Name
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/s10107-015-0958-2 | Mathematical Programming: Series A and B |
Keywords | Field | DocType |
stochastic programming | Applied mathematics,Mathematical optimization,Stochastic optimization,Computer science,Approximate solution,Stochastic programming,Computational complexity theory | Journal |
Volume | Issue | ISSN |
159 | 1-2 | 0025-5610 |
Citations | PageRank | References |
9 | 0.51 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hanasusanto, Grani Adiwena | 1 | 86 | 5.71 |
| Daniel Kuhn | 2 | 559 | 32.80 |
| Wolfram Wiesemann | 3 | 416 | 21.96 |