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 2017
  • View Item
  • edoc-Server Home
  • Elektronische Zeitschriften
  • Stochastic Programming E-print Series (SPEPS)
  • Volume 2017
  • 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 2017
  • View Item
  • edoc-Server Home
  • Elektronische Zeitschriften
  • Stochastic Programming E-print Series (SPEPS)
  • Volume 2017
  • View Item
2017-02-21Buch DOI: 10.18452/8453
Scenariao Reduction Revisited: Fundamental Limits and Gurarantees
Rujeerapaiboon, Napat
Schindler, Kilian
Kuhn, Daniel
Wiesemann, Wolfram
The goal of scenario reduction is to approximate a given discrete distributionwith another discrete distribution that has fewer atoms. We distinguishcontinuous scenario reduction, where the new atoms may be chosen freely, anddiscrete scenario reduction, where the new atoms must be chosen from among theexisting ones. Using the Wasserstein distance as measure of proximity between distributions,we identify those n-point distributions on the unit ball that are leastsusceptible to scenario reduction, i.e., that have maximum Wasserstein distanceto their closest m-point distributions for some prescribed m < n. We also providesharp bounds on the added benefit of continuous over discrete scenario reduction.Finally, to our best knowledge, we propose the first polynomial-time constant-factorapproximations for both discrete and continuous scenario reduction as wellas the first exact exponential-time algorithms for continuous scenario reduction.
Files in this item
Thumbnail
1.pdf — Adobe PDF — 1.326 Mb
MD5: 802c2a88b9df4a72fe8f5a3fab6a6434
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/8453
Permanent URL
https://doi.org/10.18452/8453
HTML
<a href="https://doi.org/10.18452/8453">https://doi.org/10.18452/8453</a>