The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group


with additional support from the Analytics Group of the Northwestern Mutual Life Insurance Company

Northwestern Mutual

On the Existence of Compact Epsilon-Approximated Formulations for Knapsack in the Original Space

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.