Scenario reduction revisited: fundamental limits and guarantees
File(s)paper.pdf (1.39 MB)
Accepted version
Author(s)
Rujeerapaiboon, N
Schindler, K
Kuhn, D
Wiesemann, W
Type
Journal Article
Abstract
The goal of scenario reduction is to approximate a given discrete distribution with another discrete distribution that has fewer atoms. We distinguish continuous scenario reduction, where the new atoms may be chosen freely, and discrete scenario reduction, where the new atoms must be chosen from among the existing ones. Using the Wasserstein distance as measure of proximity between distributions, we identify those n-point distributions on the unit ball that are least susceptible to scenario reduction, i.e., that have maximum Wasserstein distance to their closest m-point distributions for some prescribed m<n. We also provide sharp bounds on the added benefit of continuous over discrete scenario reduction. Finally, to our best knowledge, we propose the first polynomial-time constant-factor approximations for both discrete and continuous scenario reduction as well as the first exact exponential-time algorithms for continuous scenario reduction.
Date Issued
2022-01-01
Online Publication Date
2019-04-06T06:00:22Z
Date Acceptance
2018-03-27
ISSN
0025-5610
Publisher
Springer Verlag
Start Page
207
End Page
242
Journal / Book Title
Mathematical Programming, Series B
Volume
191
Copyright Statement
© Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2018. The final publication is available at Springer via https://link.springer.com/article/10.1007%2Fs10107-018-1269-1
Source Database
manual-entry
Sponsor
Engineering & Physical Science Research Council (E
Grant Number
EP/M028240/1
Subjects
Operations Research
0102 Applied Mathematics
0103 Numerical and Computational Mathematics
0802 Computation Theory and Mathematics
Publication Status
Published
Date Publish Online
2018-04-06