We consider a class of algorithms which use the combined powers of branch-and-bound, dynamic programming and rudimentary divisibility arguments for solving the zero-one knapsack problem. Our main result identifies a class of instances of the problem which are difficult to solve by such algorithms. More precisely, if reading the data takes t units of time, then the time required to solve the problem grows exponentially with the square root of t.
No takes yet. Share an insight, caveat, or question.
Vašek Chvátal (1980) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: