A PARALLEL TIME HARDWARE TRADEOFF T.H=O(2N/2) FOR THE KNAPSACK-PROBLEM

In this paper, we propose a parallel algorithm that solves a knapsack problem of size n in time T = O(n * (2n/2)epsilon) when P = O((2n/2)(1-epsilon)), 0 less-than-or-equal-to epsilon less-than-or-equal-to 1, processors are available. The algorithm needs S = O(2n/2) memory space in a shared memory. Let H (for hardware) be the number of processors plus the number of memory cells used by a parallel algorithm. The parallel algorithm that we describe here takes a linear time proportional to (n/2) to find a solution when P = O(2n/2), leading to a tradeoff T . H = O(2n/2).