# A NOTE ON THE EXTENSION COMPLEXITY OF THE KNAPSACK POLYTOPE

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 polyhedra in dimension n with extension complexity \Omega(2^\sqrt{n}).

## Article

Download

View A NOTE ON THE EXTENSION COMPLEXITY OF THE KNAPSACK POLYTOPE