Article ID: | iaor20051945 |
Country: | Netherlands |
Volume: | 154 |
Issue: | 1 |
Start Page Number: | 36 |
End Page Number: | 45 |
Publication Date: | Apr 2004 |
Journal: | European Journal of Operational Research |
Authors: | Kohli Rajeev, Krishnamurti Ramesh, Mirchandani Prakash |
Keywords: | heuristics |
This paper derives a lower bound on the average performance of a total-value greedy heuristic for the integer knapsack problem. This heuristic selects items in order of their maximum possible contribution to the solution value at each stage. We show that, as for the worst-case bound, the average performance bound for the total-value heuristic dominates the corresponding bound for the density-ordered greedy heuristic.