A NOTE ON THE EXTENSION COMPLEXITY OF THE KNAPSACK POLYTOPE

  • Sebastian Pokutta
  • Mathieu Van Vyve
    • Categories 0-1 Programming, Integer Programming, Polyhedra Tags , , Short URL: https://optimization-online.org/?p=12332

    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 PDF