Reduction Algorithm for Zero-One Single Knapsack Problems

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.

• 저널Management Science · 20(4-part-i) · 460–463
• 토픽Optimization and Packing Problems · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.20.4.460
• 저자Giorgio Ingargiola, James F. Korsh