Logo of Humboldt-Universität zu BerlinLogo of Humboldt-Universität zu Berlin
edoc-Server
Open-Access-Publikationsserver der Humboldt-Universität
de|en
Header image: facade of Humboldt-Universität zu Berlin
View Item 
  • edoc-Server Home
  • Elektronische Zeitschriften
  • Stochastic Programming E-print Series (SPEPS)
  • Volume 2015
  • View Item
  • edoc-Server Home
  • Elektronische Zeitschriften
  • Stochastic Programming E-print Series (SPEPS)
  • Volume 2015
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.
All of edoc-ServerCommunity & CollectionTitleAuthorSubjectThis CollectionTitleAuthorSubject
PublishLoginRegisterHelp
StatisticsView Usage Statistics
All of edoc-ServerCommunity & CollectionTitleAuthorSubjectThis CollectionTitleAuthorSubject
PublishLoginRegisterHelp
StatisticsView Usage Statistics
View Item 
  • edoc-Server Home
  • Elektronische Zeitschriften
  • Stochastic Programming E-print Series (SPEPS)
  • Volume 2015
  • View Item
  • edoc-Server Home
  • Elektronische Zeitschriften
  • Stochastic Programming E-print Series (SPEPS)
  • Volume 2015
  • View Item
2015-04-22Buch DOI: 10.18452/8446
A Comment on "Computational Complexityof Stochastic Programming Problems"
Hanasusanto, Grani A.
Kuhn, Daniel
Wiesemann, Wolfram
Although stochastic programming problems were always believed to be computationally chal-lenging, this perception has only recently received a theoretical justification by the seminal workof 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 evenif the random problem data is governed by independent uniform distributions. We show thatDyer and Stougie's proof is not correct, and we offer a correction which establishes the strongerresult that even the approximate solution of such problems is #P-hard for a sufficiently highaccuracy. We also prove that the approximate solution of linear two-stage stochastic programswith random recourse is strongly #P-hard.
Files in this item
Thumbnail
2.pdf — Adobe PDF — 317.9 Kb
MD5: b792122e48f8b314be5370b0dcdca7df
Cite
BibTeX
EndNote
RIS
InCopyright
Details
DINI-Zertifikat 2019OpenAIRE validatedORCID Consortium
Imprint Policy Contact Data Privacy Statement
A service of University Library and Computer and Media Service
© Humboldt-Universität zu Berlin
 
DOI
10.18452/8446
Permanent URL
https://doi.org/10.18452/8446
HTML
<a href="https://doi.org/10.18452/8446">https://doi.org/10.18452/8446</a>