## 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