Hard Knapsack Problems
Operations Research
1980
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.
- DOI
- 10.1287/opre.28.6.1402
- Volume
- 28 (6)
- Pages
- 1402-1411
- Language
- en
- Export
- BibTeX
- Sources
- crossref