TY - GEN
T1 - On the parallel computation for the knapsack problem
AU - Yao, Andrew Chi Chih
N1 - Publisher Copyright:
© 1981 ACM.
PY - 1981/5/11
Y1 - 1981/5/11
N2 - 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 ≤ √n/2.
AB - 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 ≤ √n/2.
KW - Branching operations
KW - Complexity
KW - Knapsack
KW - Parallel computation
UR - https://www.scopus.com/pages/publications/0038945156
U2 - 10.1145/800076.802465
DO - 10.1145/800076.802465
M3 - 会议稿件
AN - SCOPUS:0038945156
SN - 0897910419
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 123
EP - 127
BT - Conference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981
PB - Association for Computing Machinery
T2 - 13th Annual ACM Symposium on Theory of Computing, STOC 1981
Y2 - 11 June 1981 through 13 June 1981
ER -