On the existence of compact εε-approximated formulations for knapsack in the original space

We show that there exists a family PP of Knapsack polytopes such that for each P∈PP∈P and each ε>0ε>0, any εε-approximated formulation of PP in the original space RnRn requires a number of inequalities that is super-polynomial in nn. This answers a question by Bienstock and McClosky (2012). We also prove that, for any down-monotone polytope, an εε-approximated formulation in the original space can be obtained with inequalities using at most O(1εmin{log(n/ε),n}) different coefficients.