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
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