A total-value greedy heuristic for the integer knapsack problem

A total-value greedy heuristic for the integer knapsack problem

0.00 Avg rating0 Votes
Article ID: iaor19931159
Country: Netherlands
Volume: 12
Issue: 2
Start Page Number: 65
End Page Number: 71
Publication Date: Aug 1992
Journal: Operations Research Letters
Authors: ,
Keywords: heuristics, programming: integer
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 correspoding lower bound for the density-ordered greedy heuristic.

Reviews

Required fields are marked *. Your email address will not be published.