Journal article

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

We show that there exists a family P of Knapsack polytopes such that for each P is an element of P 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(1/epsilon min{log(n/epsilon), n}) different coefficients. (C) 2015 Elsevier B.V. All rights reserved.


Related material