000224448 001__ 224448
000224448 005__ 20180407112159.0
000224448 0247_ $$2doi$$a10.1007/s10107-018-1269-1
000224448 037__ $$aARTICLE
000224448 245__ $$aScenario Reduction Revisited: Fundamental Limits and Guarantees
000224448 260__ $$c2018
000224448 269__ $$a2018
000224448 336__ $$aJournal Articles
000224448 500__ $$aAvailable from Optimization Online
000224448 520__ $$aThe 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.
000224448 6531_ $$aScenario reduction
000224448 6531_ $$aWasserstein distance
000224448 6531_ $$aConstant-factor approximation algorithm
000224448 6531_ $$ak-median clustering
000224448 6531_ $$ak-means clustering
000224448 700__ $$0247784$$aRujeerapaiboon, Napat$$g240295
000224448 700__ $$0250533$$aSchindler, Kilian$$g272900
000224448 700__ $$0247589$$aKuhn, Daniel$$g239987
000224448 700__ $$aWiesemann, Wolfram
000224448 773__ $$tMathematical Programming
000224448 8560_ $$fdaniel.kuhn@epfl.ch
000224448 8564_ $$uhttp://www.optimization-online.org/DB_HTML/2017/01/5816.html$$zURL
000224448 909C0 $$0252496$$pRAO$$xU12788
000224448 909C0 $$0252496$$malexandra.vonschack@epfl.ch$$pRAO$$xU12788
000224448 909CO $$ooai:infoscience.tind.io:224448$$pCDM$$particle
000224448 917Z8 $$x239987
000224448 917Z8 $$x239987
000224448 937__ $$aEPFL-ARTICLE-224448
000224448 973__ $$aEPFL$$rREVIEWED$$sPUBLISHED
000224448 980__ $$aARTICLE