Rajeev Kohli

A Total-Value Greedy Heuristic for the Integer Knapsack Problem

Coauthor(s): Ramesh Krishnamurti.

Abstract:
This paper examines a new greedy heuristic for the integer knapsack problem. The proposed heuristic selects items in non-increasing order of their maximum possible contribution to the solution value given the available knapsack capacity at each step. The lower bound on the performance ratio for this "total-value" greedy heuristic is shown to dominate the corresponding lower bound for the density-ordered greedy heuristic.

Source: Operations Research Letters
Exact Citation:
Kohli, Rajeev, and Ramesh Krishnamurti. "A Total-Value Greedy Heuristic for the Integer Knapsack Problem." Operations Research Letters 12, no. 2 (August 1992): 65-71.
Volume: 12
Number: 2
Pages: 65-71
Date: 8 1992