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

Yuri Faenza, Laura Sanità

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

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 languageEnglish
Pages (from-to)339-342
Number of pages4
JournalOperations Research Letters
Volume43
Issue number3
DOIs
Publication statusPublished - 30 May 2015
Externally publishedYes

Keywords

  • Approximated formulation
  • Integer programming
  • Knapsack

Fingerprint Dive into the research topics of 'On the existence of compact ε-approximated formulations for knapsack in the original space'. Together they form a unique fingerprint.

  • Cite this