JOINT PERFORMANCE OF GREEDY HEURISTICS FOR THE INTEGER KNAPSACK-PROBLEM

This paper analyzes the worst-case performance of combinations of gree dy heuristics for the integer knapsack problem. If the knapsack is lar ge enough to accomodate at least rn units of any item, then the joint performance of the total-value and density-ordered greedy heuristics i s no smaller than (m + 1)/(m + 2). For combinations of greedy heuristi cs that do not involve both the density-ordered and total-value greedy heuristics, the worst-case performance of the combination is no bette r than the worst-case performance of the single best heuristic in the combination.