- | ||||
|
![]()
|
A NOTE ON THE EXTENSION COMPLEXITY OF THE KNAPSACK POLYTOPE
Sebastian Pokutta(sebastian.pokutta 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 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 | |
![]() |