A NOTE ON THE EXTENSION COMPLEXITY OF THE KNAPSACK POLYTOPE

Sebastian Pokutta(sebastian.pokuttaisye.gatech.edu)
Mathieu Van Vyve(mathieu.vanvyveuclouvain.be)

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

Keywords: extension complexity, knapsack polytope, approximation algorithms.

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Integer Programming (0-1 Programming )

Category 3: Integer Programming (Other )

Citation:

Download: [PDF]

Entry Submitted: 02/20/2013
Entry Accepted: 02/24/2013
Entry Last Modified: 02/20/2013

Modify/Update this entry