Abstract
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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 15-20 |
| Number of pages | 6 |
| Journal | Acta Cybernetica |
| Volume | 10 |
| Issue number | 1-2 |
| State | Published - 1991 |
Bibliographical note
Publisher Copyright:© 1991 University of Szeged Institute of Informatics. All rights reserved.
Fingerprint
Dive into the research topics of 'Heuristics for the 0-1 min-knapsack problem'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS