*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
TITLE: Some Lower Bounds on Sparse Outer Approximations of Polytopes
SPEAKER: Andres Iroume
ABSTRACT:
Trying to understand the use of sparse cutting-planes in integer programming solvers, a recent paper by Dey, Molinaro and Wang studied how well polytopes are approximated by using only sparse valid-inequalities. In this talk, 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.
