A simple 0.5-bounded greedy algorithm for the 0/1 knapsack-problem

A simple 0.5-bounded greedy algorithm for the 0/1 knapsack-problem

0.00 Avg rating0 Votes
Article ID: iaor19951116
Country: United States
Volume: 42
Issue: 3
Start Page Number: 173
End Page Number: 177
Publication Date: May 1992
Journal: Information Processing Letters
Authors: , , ,
Keywords: heuristics
Abstract:

The Non-Increasing First Fit (NIFF) greedy algorithm for the 0/1 knapsack problem does not provide a founded solution. In this paper a simple modification of this greedy procedure is proposed whose solution is no worse than the solution found by the NIFF algorithm and is guaranteed to be 0.5-bounded. A further modification of the proposed algorithm is shown to impove the bound to 1/3 for the special case of the problem when profit per unit weight is the same for all objects. The bounds obtained are shown to be tight. Experiments were performed with random instances of the problem in order to compare the quality of the solution of this algorithm and that of the NIFF algorithm relative to the optimal solution.

Reviews

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