Heuristics for the 0-1 min-knapsack problem
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 n...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Published: |
1991
|
| Series: | Acta cybernetica
10 No. 1-2 |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Subjects: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12488 |
| Summary: | 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. |
|---|---|
| Physical Description: | 15-20 |
| ISSN: | 0324-721X |