Scenariao Reduction Revisited: Fundamental Limits and Gurarantees

Abstract

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.