Yet harder knapsack problems

S. Jukna and G. Schnitger

Abstract

Already 30 years ago, Chv\'atal has shown that some instances of the zero-one knapsack problem cannot be solved in polynomial time using a particular type of branch-and-bound algorithms based on relaxations of linear programs together with some rudimentary cutting-plane arguments as bounding rules.

We extend this result by proving an exponential lower bound in a more general class of branch-and-bound and dynamic programming algorithms which are allowed to: use memoization and arbitrarily powerful bound rules to detect and remove subproblems leading to no optimal solution.