Institution: Stanford University, Department of Computer Science

Title: On the parallel computation for the knapsack problem

Author: Yao, Andrew Chi-Chih

Date: November 1980

Abstract: We are interested in the complexity of solving the knapsack problem with n input real numbers on a parallel computer with real arithmetic and branching operations. A processor-time tradeoff constraint is derived; in particular, it is shown that an exponential number of processors have to be used if the problem is to be solved in time $t \le {\sqrt{n}}/2$.

http://i.stanford.edu/pub/cstr/reports/cs/tr/80/827/CS-TR-80-827.pdf