Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
482421 | European Journal of Operational Research | 2007 | 10 Pages |
Abstract
In this paper, we suggest a parallel algorithm based on a shared memory SIMD architecture for solving an n item subset-sum problem in time O(2n/2/p) by using p = 2q processors, 0⩽q⩽n2-2log2n. This approach is an optimal and scalable parallelization of the well known two-list Horowitz and Sahni’s algorithm, which is still the best complexity time bound for solving the Knapsack problem in a serial environment.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
C.A.A. Sanches, N.Y. Soma, H.H. Yanasse,