Total variation bounds on the expectation of periodic functions with applications to recourse approximations

Ward Romeijnders, Maarten H. van der Vlerk, Willem K. Klein Haneveld

OnderzoeksoutputAcademicpeer review

9 Citaten (Scopus)
4 Downloads (Pure)


We derive a lower and upper bound for the expectation of periodic functions, depending on the total variation of the probability density function of the underlying random variable. Using worst-case analysis we derive tighter bounds for functions that are periodically monotone. These bounds can be used to evaluate the performance of approximations for both continuous and integer recourse models. In this paper, we introduce a new convex approximation for totally unimodular recourse models, and we show that this convex approximation has the best worst-case error bound possible, improving previous bounds with a factor 2. Moreover, we use similar analysis to derive error bounds for two types of discrete approximations of continuous recourse models with continuous random variables. Furthermore, we derive a tractable Lipschitz constant for pure integer recourse models.
Originele taal-2English
Pagina's (van-tot)3-46
Aantal pagina's44
TijdschriftMathematical Programming
Nummer van het tijdschrift1
Vroegere onlinedatum30-okt-2014
StatusPublished - mei-2016

Citeer dit