Timm Oertel: IP to LP proximity

Abstract:
A classic result by Cook et al. bounds the proximity between optimal solutions of integer linear programs and optimal solutions of the corresponding linear relaxations. Their bound is given in terms of the number of variables and in terms of the maximum sub-determinants of the underlying systems of linear inequalities. In this talk, I will give an overview on more recent proximity results for integer linear programs in standard form. Most notably, these bounds do not depend on the number of variables. I will highlight the use of the classical Steinitz Lemma.