IRUS Total

Scenario reduction revisited: fundamental limits and guarantees

File Description SizeFormat 
paper.pdfAccepted version1.43 MBAdobe PDFView/Open
Title: Scenario reduction revisited: fundamental limits and guarantees
Authors: Rujeerapaiboon, N
Schindler, K
Kuhn, D
Wiesemann, W
Item Type: Journal Article
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.
Issue Date: 1-Jan-2022
Date of Acceptance: 27-Mar-2018
URI: http://hdl.handle.net/10044/1/60193
DOI: 10.1007/s10107-018-1269-1
ISSN: 0025-5610
Publisher: Springer Verlag
Start Page: 207
End Page: 242
Journal / Book Title: Mathematical Programming, Series B
Volume: 191
Copyright Statement: © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2018. The final publication is available at Springer via https://link.springer.com/article/10.1007%2Fs10107-018-1269-1
Sponsor/Funder: Engineering & Physical Science Research Council (E
Funder's Grant Number: EP/M028240/1
Keywords: Operations Research
0102 Applied Mathematics
0103 Numerical and Computational Mathematics
0802 Computation Theory and Mathematics
Publication Status: Published
Online Publication Date: 2018-04-06
Appears in Collections:Imperial College Business School