"A Total-Value Greedy Heuristic for the Integer Knapsack Problem"

Rajeev Kohli, Ramesh Krishnamurti

© Operations Research Letters, August 1992
Volume: 12 | Issue: 2 | Pages: 65-71

Publication type: Journal article

Research Archive Topic: Operations, Strategy

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.

Download PDF

 

Each author name for a Columbia Business School faculty member is linked to a faculty research page, which lists additional publications by that faculty member.

Each topic is linked to an index of publications on that topic.