Comments on parallel algorithms for the knapsack problem. (Q1853236): Difference between revisions

\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.