Convex approximations for totally unimodular integerrecourse models: A uniform error bound

Abstract

We consider a class of convex approximations for totally unimodular (TU) integer recourse models and derive a uniform error bound by exploiting properties of the total variation of the probability density functions involved. For simple integer recourse models this error bound is tight and improves the existing one by a factor 2, whereas for TU integer recourse modelsthis is the first nontrivial error bound available. The bound ensures that theperformance of the approximations is good as long as the total variations of the densities of all random variables in the model are small enough.