Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142098 | Operations Research Letters | 2015 | 4 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Yuri Faenza, Laura Sanità,