Comments on parallel algorithms for the knapsack problem.
\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.
- A parallel two-list algorithm for the knapsack problem
- scientific article; zbMATH DE number 2075843 (Why is no real title available?)
- A parallel time/hardware tradeoff T.H=O(2/sup n/2/) for the knapsack problem
- Approximate algorithms for the Knapsack problem on parallel computers
- An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem
- Observations on optimal parallelizations of two-list algorithm
This page was built for publication: Comments on parallel algorithms for the knapsack problem.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853236)
