TITLE

Merging and Sorting Applied to the Zero-One Knapsack Problem

AUTHOR(S)
Ahrens, J. H.; Finke, G.
PUB. DATE
November 1975
SOURCE
Operations Research;Nov/Dec75, Vol. 23 Issue 6, p1099
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
Branch-and-bound algorithms are adequate for the solution of a wide range of 0-1 knapsack problems. It is shown that the simplest method of branching is as good as any. However, problems with highly correlated large weights and values quickly become unsolvable in a reasonable time. This paper develops algorithms that are aimed specifically at the hardest possible examples. The new methods use merging and sorting ideas and require a moderate amount of additional memory space. They are, however, faster by factors far in excess of 1000 in many cases, thereby extending considerably the range of practically solvable 0-1 knapsack problems.
ACCESSION #
6663707

 

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics