Title: Scenario Reduction Revisited: Fundamental Limits and Guarantees,
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.