An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem

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.