-

 

 

 




Optimization Online





 

A NOTE ON THE EXTENSION COMPLEXITY OF THE KNAPSACK POLYTOPE

Sebastian Pokutta(sebastian.pokutta***at***isye.gatech.edu)
Mathieu Van Vyve(mathieu.vanvyve***at***uclouvain.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


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society