Comments on parallel algorithms for the knapsack problem. (Q1853236): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 05:56, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Comments on parallel algorithms for the knapsack problem. |
scientific article |
Statements
Comments on parallel algorithms for the knapsack problem. (English)
0 references
21 January 2003
0 references
\textit{H. K.-C. Chang}, \textit{J. J.-R. Chen} and \textit{S. J. Shyu} [Parallel Comput. 20, 233--243 (1994)] introduced a parallel algorithm based on a shared memory SIMD architecture for the generation phase of the classic \textit{E. Horowitz} and \textit{S. Sahni} [J. Assoc. Comput. Mach. 21, 277--292 (1974; Zbl 0329.90046)] 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 \textit{D. R. Lou} and \textit{C. C. Chang} [Parallel Comput. 22, 1985--1996 (1997; Zbl 0906.68079)] algorithm.
0 references