tlooto
Sign up
Computer ScienceMathematics

Heuristics for the 0–1 min-knapsack problem

J. Csirik, J. Frenk, M. Labbé, Shuzhong Zhang

1991.9.1Acta Cybernetica

tlooto Summary

This work studies a greedy-type heuristic and refined it to obtain a new heuristic with a worst-case bound of 3/2 that is applicable to the 0-1 min-knapsack problem.

Abstract

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

Citation format

CSIRIK, J., et al. Heuristics for the 0–1 min-knapsack problem. Acta Cybernetica, 1991, 10: 15–20.