Reduction Algorithm for Zero-One Single Knapsack Problems
Giorgio P. Ingargiola, James F. Korsh · Management Science · 1973
A simple algorithm is described for the reduction of 0-1 single knapsack problems to significantly smaller problems. The time required by the reduction algorithm is proportional to the number of variables. When used in conjunction with available algorithms for knapsack problems it substantially reduces total time and space requirements.
Cited by 79 works. doi:10.1287/mnsc.20.4.460
Authors
References
- Discrete-Variable Extremum Problems
- A Linear Programming Approach to the Cutting Stock Problem—Part II
- A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
- Integer Programming Algorithms: A Framework and State-of-the-Art Survey
- A Branch and Bound Algorithm for the Knapsack Problem
- A Branch Search Algorithm for the Knapsack Problem
- An Enumeration Algorithm for Knapsack Problems