Sarkar, U. K. ; Chakrabarti, P. P. ; Ghose, S. ; De Sarkar, S. C. (1992) A simple 0.5-bounded greedy algorithm for the 0/1 knapsack problem Information Processing Letters, 42 (3). pp. 173-177. ISSN 0020-0190
Full text not available from this repository.
Official URL: http://linkinghub.elsevier.com/retrieve/pii/002001...
Related URL: http://dx.doi.org/10.1016/0020-0190(92)90143-J
Abstract
The Non-Increasing First Fit (NIFF) greedy algorithm for the 0/1 knapsack problem does not provide a bounded 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 improve 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.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| Keywords: | Greedy Algorithm; Approximation Algorithm; 0/1 Knapsack Problem; Non-increasing First Fit; Algorithms |
| ID Code: | 5958 |
| Deposited On: | 19 Oct 2010 10:03 |
| Last Modified: | 20 May 2011 09:49 |
Repository Staff Only: item control page
