A note on the extension complexity of the knapsack polytope

作者：Pokutta Sebastian; Van Vyve Mathieu^*

来源：Operations Research Letters, 2013, 41(4): 347-350.

DOI：10.1016/j.orl.2013.03.010

• Extension complexity
• Knapsack polytope
• Approximation algorithms

We show that there are 0-1 and unbounded knapsack polytopes with super-polynomial extension complexity. More specifically, for each n is an element of N we exhibit 0-1 and unbounded knapsack polytopes in dimension n with extension complexity Omega(2(root n)).

• 出版日期2013-7