Optimization Online


Scenario Reduction Revisited: Fundamental Limits and Guarantees

Napat Rujeerapaiboon(napat.rujeerapaiboon***at***epfl.ch)
Kilian Schindler(kilian.schindler***at***epfl.ch)
Daniel Kuhn(daniel.kuhn***at***epfl.ch)
Wolfram Wiesemann(ww***at***imperial.ac.uk)

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.

Keywords: scenario reduction, Wasserstein distance, constant-factor approximation algorithm, k-median clustering, k-means clustering

Category 1: Stochastic Programming

Category 2: Robust Optimization

Category 3: Linear, Cone and Semidefinite Programming


Download: [PDF]

Entry Submitted: 01/15/2017
Entry Accepted: 01/15/2017
Entry Last Modified: 01/15/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society