  


Scenario Reduction Revisited: Fundamental Limits and Guarantees
Napat Rujeerapaiboon(napat.rujeerapaiboonepfl.ch) 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 npoint distributions on the unit ball that are least susceptible to scenario reduction, i.e., that have maximum Wasserstein distance to their closest mpoint 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 polynomialtime constantfactor approximations for both discrete and continuous scenario reduction as well as the first exact exponentialtime algorithms for continuous scenario reduction. Keywords: scenario reduction, Wasserstein distance, constantfactor approximation algorithm, kmedian clustering, kmeans clustering Category 1: Stochastic Programming Category 2: Robust Optimization Category 3: Linear, Cone and Semidefinite Programming Citation: Download: [PDF] Entry Submitted: 01/15/2017 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  