224448
20190615115433.0
doi
10.1007/s10107-018-1269-1
ARTICLE
Scenario Reduction Revisited: Fundamental Limits and Guarantees
2018
2018
Journal Articles
Available from Optimization Online
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.
Scenario reduction
Wasserstein distance
Constant-factor approximation algorithm
k-median clustering
k-means clustering
247784
Rujeerapaiboon, Napat
240295
250533
Schindler, Kilian
272900
247589
Kuhn, Daniel
239987
Wiesemann, Wolfram
Mathematical Programming
daniel.kuhn@epfl.ch
http://www.optimization-online.org/DB_HTML/2017/01/5816.html
URL
oai:infoscience.tind.io:224448
CDM
article
GLOBAL_SET
252496
RAO
U12788
239987
239987
EPFL-ARTICLE-224448
EPFL
REVIEWED
PUBLISHED
ARTICLE