We show that there exists a family of Knapsack polytopes such that, for each polytope P from this 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, an { \epsilon}-approximated formulation in the original space can be obtained with inequalities using at most O(min{ log(n/{ \epsilon}),n}/{ \epsilon}) different coefficients.
Categories: math.OC cs.DM math.CO