Average performance of greedy heuristics for the integer knapsack problem

Average performance of greedy heuristics for the integer knapsack problem

0.00 Avg rating0 Votes
Article ID: iaor20051945
Country: Netherlands
Volume: 154
Issue: 1
Start Page Number: 36
End Page Number: 45
Publication Date: Apr 2004
Journal: European Journal of Operational Research
Authors: , ,
Keywords: heuristics
Abstract:

This paper derives a lower bound on the average performance of a total-value greedy heuristic for the integer knapsack problem. This heuristic selects items in order of their maximum possible contribution to the solution value at each stage. We show that, as for the worst-case bound, the average performance bound for the total-value heuristic dominates the corresponding bound for the density-ordered greedy heuristic.

Reviews

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