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.
Kohli, Rajeev, Ramesh Krishnamurti, and Prakash Mirchandani. "Average Performance of Greedy Heuristics for the Integer Knapsack Problem." European Journal of Operational Research 154, no. 1 (April 1, 2004): 36-45.
Each author name for a Columbia Business School faculty member is linked to a faculty research page, which lists additional publications by that faculty member.
Each topic is linked to an index of publications on that topic.