Article ID: | iaor19931159 |
Country: | Netherlands |
Volume: | 12 |
Issue: | 2 |
Start Page Number: | 65 |
End Page Number: | 71 |
Publication Date: | Aug 1992 |
Journal: | Operations Research Letters |
Authors: | Kohli Rajeev, Krishnamurti Ramesh |
Keywords: | heuristics, programming: integer |
This paper examines a new greedy heuristic for the integer knapsack problem. The proposed heuristic selects items in non-increasing order of their maximum possible contribution to the solution value given the available knapsack capacity at each step. The lower bound on the performance ratio for this ‘total-value’ greedy heuristic is shown to dominate the correspoding lower bound for the density-ordered greedy heuristic.