๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Some exact algorithms for the knapsack sharing problem

โœ Scribed by Takeo Yamada; Mayumi Futakawa; Seiji Kataoka

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
446 KB
Volume
106
Category
Article
ISSN
0377-2217

No coin nor oath required. For personal study only.

โœฆ Synopsis

The knapsack sharing problem (KSP) is formulated as an extension to the ordinary knapsack problem. The KSP is .AlP-hard. We present a branch-and-bound algorithm and a binary search algorithm to solve this problem to optimality. These algorithms are implemented and computational experiments are carded out to analyse the behavior of the developed algorithms. As a result, we find that the binary search algorithm solves KSPs with up to 20 000 variables in less than a minute in our computing environment. (~) 1998 Elsevier Science B.V.

๐Ÿ“œ SIMILAR VOLUMES

An exact algorithm for large multiple kn
An exact algorithm for large multiple knapsack problems
โœ David Pisinger ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 137 KB

The Multiple Knapsack Problem (MKP) is the problem of assigning a subset of n items to m distinct knapsacks, such that the total proยฎt sum of the selected items is maximized, without exceeding the capacity of each of the knapsacks. The problem has several applications in naval as well as ยฎnancial ma

Comments on parallel algorithms for the
Comments on parallel algorithms for the knapsack problem
โœ Carlos Alberto Alonso Sanches; Nei Yoshihiro Soma; Horacio Hideki Yanasse ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 65 KB

Chang et al. [Parallel Comput. (1994) 233] introduced a parallel algorithm based on a shared memory SIMD architecture for the generation phase of the classic Horowitz and Sahni [J. ACM 21(2) (1974) 277] two-list serial algorithm for the knapsack problem. They claimed that their parallel generation p