1991
Heuristics for the 0-1 Min-Knapsack Problem
Publication
Publication
University of Szeged. Acta Cybernetica , Volume 10 - Issue 1-2 p. 15- 20
The 0-1 min-knapsack problem consists in finding a subset of items such that the sum of their sizes is larger than or equal to a given constant and the sum of their costs is minimized. We first study a greedy-type heuristic having a worst-case bound of 2. This heuristic is then refined to obtain a new one with a worst-case bound of 3/2.
| Additional Metadata | |
|---|---|
| hdl.handle.net/1765/11735 | |
| University of Szeged. Acta Cybernetica | |
| Organisation | Erasmus School of Economics |
|
Frenk, H., Csirik, J., Labbé, M., & Zhang, S. (1991). Heuristics for the 0-1 Min-Knapsack Problem. University of Szeged. Acta Cybernetica, 10(1-2), 15–20. Retrieved from http://hdl.handle.net/1765/11735 |
|
