Observations on optimal parallelizations of two-list algorithm
For more than three decades, the very well known and famous two-list Horowitz and Sahni algorithm [3] remains the serial upper-bound for the 01 Knapsack problem with n  items (KP01) in a time bounded by O(2n/2) O ( 2 n / 2 ) . Recently, Chedid [2] suggested an optimal parallelization for that algorithm to a KP01 variation  the subset-sum problem  in a PRAM CREW with p=2n/8 p = 2 n / 8 processors. It is presented here that, in addition to be incomplete, the Chedid result is a particular case given by Sanches et al. [6].
two-list algorithm knapsack problem subset-sum problem parallel algorithm