Report Number: CS-TR-80-827
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$.