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.
On the existence of compact ε-approximated formulations for knapsack in the original space
Sanita Laura
2015
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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
