Heuristics for the 0-1 Min-Knapsack Problem
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.
|University of Szeged. Acta Cybernetica|
|Organisation||Erasmus School of Economics|
Frenk, J.B.G, 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