An improved direct descent algorithm for binary knapsack problems (Q1115799)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4087423
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | An improved direct descent algorithm for binary knapsack problems |
scientific article; zbMATH DE number 4087423 |
Statements
An improved direct descent algorithm for binary knapsack problems (English)
0 references
1989
0 references
Several efficient algorithms for the solution of the binary knapsack problem have appeared in the literature. The direct descent algorithm is generally recognized as one of the most efficient. This paper improves the direct descent algorithm through a more general fathom and backtrack methodology and stronger reduction tests. The efficiency of these improvements is verified through extensive computational testing.
0 references
binary knapsack
0 references
direct descent algorithm
0 references
general fathom and backtrack methodology
0 references
reduction tests
0 references
computational testing
0 references
0.8002007007598877
0 references
0.7960807085037231
0 references
0.7909564971923828
0 references
