Yet harder knapsack problems

Already 30 years ago, Chvátal 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.

Authors

• Stasys Jukna
• Georg Schnitger

Keywords

• Branch and bound
• Dynamic programming
• Memoization
• Branching program
• Knapsack
• Perfect matching