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(2^n/2/p) by using p = 2^q processors, 0 ⩽ q ⩽ n/2 − 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.