BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-80-827
       ENTRY:: June 08, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: On the parallel computation for the knapsack problem
        TYPE:: Technical Report
      AUTHOR:: Yao, Andrew Chi-Chih
        DATE:: November 1980
       PAGES:: 12
    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$.
       NOTES:: [Adminitrivia V1/Prg/19950608]
         END:: STAN//CS-TR-80-827