Laura Sanita, Prof. at Combinatorics & Optimization Department, University of Waterloo, Ontario, Canada
Date and Time: Apr 29, 2015 (12:30 PM)
Location: Orchard room (3280) at the Wisconsin Institute for Discovery Building
We show that there exists a family of Knapsack polytopes such that for each P in the family and each epsilon>0, any epsilon-approximated formulation of P in the original space R^n requires a number of inequalities that is super-polynomial in n. This answers a question by Bienstock and McClosky (2012). We also prove that, for any down-monotone polytope and any fixed epsilon > 0, an epsilon approximated formulation in the original space can be obtained with inequalities using at most O(log n) different coefficients. Joint work with Yuri Faenza.