Rajeev Kohli

Joint Performance of Greedy Heuristics for the Integer Knapsack Problem

Coauthor(s): Ramesh Krishnamurti.

Abstract:
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
Exact Citation:
Kohli, Rajeev, and Ramesh Krishnamurti. "Joint Performance of Greedy Heuristics for the Integer Knapsack Problem." Discrete Applied Mathematics 56 (January 9, 1995): 37-48.
Volume: 56
Pages: 37-48
Date: 9 1 1995