Heuristics for the 0-1 min-knapsack problem

Csirik János: Heuristics for the 0-1 min-knapsack problem. In: Acta cybernetica, (10) 1-2. pp. 15-20. (1991)

[thumbnail of cybernetica_010_numb_001_002_015-020.pdf]
Preview
Cikk, tanulmány, mű
cybernetica_010_numb_001_002_015-020.pdf

Download (582kB) | Preview

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.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 1991
Volume: 10
Number: 1-2
ISSN: 0324-721X
Page Range: pp. 15-20
Language: English
Place of Publication: Szeged
Related URLs: http://acta.bibl.u-szeged.hu/38493/
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Bibliogr.: 20. p. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:26
Last Modified: 2022. Jun. 13. 08:07
URI: http://acta.bibl.u-szeged.hu/id/eprint/12488

Actions (login required)

View Item View Item