Thursday, July 23, 2015 4:00 pm
-
4:00 pm
EDT (GMT -04:00)
Title: On the existence of compact epsilon-approximated formulations for Knapsack in the original space
Speaker: | Laura Sanita |
Affiliation: | University of Waterloo |
Room: | MC 6486 |
Abstract:
Abstract: 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.