Abstract
We show that there exists a family P of Knapsack polytopes such that for each P∈P and each ε>0, any ε-approximated formulation of P in the original space Rn 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 ε-approximated formulation in the original space can be obtained with inequalities using at most O(1εminlog(n/ε),n) different coefficients.
Original language | English |
---|---|
Pages (from-to) | 339-342 |
Number of pages | 4 |
Journal | Operations Research Letters |
Volume | 43 |
Issue number | 3 |
DOIs | |
Publication status | Published - 30 May 2015 |
Externally published | Yes |
Keywords
- Approximated formulation
- Integer programming
- Knapsack