Joint Performance of Greedy Heuristics for the Integer Knapsack Problem
Coauthor(s): Ramesh Krishnamurti.
This paper analyzes the worst-case performance of combinations of greedy heuristics for the integer knapsack problem. If the knapsack is large enough to accomodate at least m units of any item, then the joint performance of the total-value and density-ordered greedy heuristics is no smaller than (m + 1)/(m + 2). For combinations of greedy heuristics that do not involve both the density-ordered and total-value greedy heuristics, the worst-case performance of the combination is no better than the worst-case performance of the single best heuristic in the combination.
Source: Discrete Applied Mathematics
Kohli, Rajeev, and Ramesh Krishnamurti. "Joint Performance of Greedy Heuristics for the Integer Knapsack Problem." Discrete Applied Mathematics 56 (January 9, 1995): 37-48.