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.

hdl.handle.net/1765/11735
University of Szeged. Acta Cybernetica
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