A note on the extension complexity of the knapsack polytope

Pokutta, Sebastian;Van Vyve, Mathieu
(2013) Operations Research Letters — Vol. 41, n° 4, p. 347-350 (2013)

Files

Rep2520.pdf
  • Closed Access
  • Adobe PDF
  • 395.02 KB
Request a copy

Details

Authors
Abstract
We show that there are 0-1 and unbounded knapsack polytopes with super-polynomial extension complexity. More specifically, for each $n \in N$ we exhibit 0-1 and unbounded knapsack polytopes in dimension $n$ with extension complexity $\Omega(2^{\sqrt{n}})$.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Pokutta, S., & Van Vyve, M. (2013). A note on the extension complexity of the knapsack polytope. Operations Research Letters, 41(4), 347-350. https://doi.org/10.1016/j.orl.2013.03.010 (Original work published 2013)