𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Comments on parallel algorithms for the knapsack problem

✍ Scribed by Carlos Alberto Alonso Sanches; Nei Yoshihiro Soma; Horacio Hideki Yanasse

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
65 KB
Volume
28
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

✦ Synopsis

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 phase could be accomplished in time Oððn=8Þ 2 Þ and in space Oð2 n=4 Þ with Oð2 n=8 Þ processors.

We prove that their results are not correct, i.e., that the suggested scheme time and space complexity should be bounded, instead, by Oðn2 n=2 Þ and Oð2 n=2 Þ, respectively. These results also invalidate the performance analysis of the more recent Lou and Chang [Parallel Comput. (1997) 1985] algorithm.

πŸ“œ SIMILAR VOLUMES

A parallel two-list algorithm for the kn
A parallel two-list algorithm for the knapsack problem
✍ Der-Chyuan Lou; Chin-Chen Chang πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 695 KB

An n-element knapsack problem has 2" possible solutions to search over, so a task which can be accomplished in 2" trials if an exhaustive search is used. Due to the exponential time in solving the knapsack problem, the problem is considered to be very hard. In the past decade, much effort has been d

Fast and Scalable Parallel Algorithms fo
Fast and Scalable Parallel Algorithms for Knapsack-like Problems
✍ Afonso Ferreira; John Michael Robson πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 403 KB

We present two new algorithms for searching in sorted X Ψ‰ Y Ψ‰ R Ψ‰ S, one based on heaps and the other on sampling. Each of the algorithms runs in time O(n 2 log n) (n being the size of the sorted arrays X, Y, R, and S). Hence in each case, by constructing arrays of size n ‫؍‬ O(2 s/4 ), we obtain a

Some exact algorithms for the knapsack s
Some exact algorithms for the knapsack sharing problem
✍ Takeo Yamada; Mayumi Futakawa; Seiji Kataoka πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 446 KB

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 carde