Some lower bounds on sparse outer approximations of polytopes

As a means to understand the use of sparse cutting-planes in integer programming solvers, the paper Dey et al. (2014) studied how well polytopes are approximated by using only sparse valid-inequalities. We consider “less-idealized” questions such as: effect of sparse inequalities added to linear-programming relaxation, effect on approximation by addition of a budgeted number of dense valid-inequalities, sparse-approximation of polytope under every rotation and approximation by sparse inequalities in specific directions.