Yet harder knapsack problems |
| |
Authors: | Stasys Jukna Georg Schnitger |
| |
Affiliation: | University of Frankfurt, Institute of Computer Science, D-60054 Frankfurt, Germany |
| |
Abstract: | 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. |
| |
Keywords: | Branch and bound Dynamic programming Memoization Branching program Knapsack Perfect matching |
本文献已被 ScienceDirect 等数据库收录! |