Optimal parallel algorithms for the knapsack problem without memory conflicts |
| |
| Authors: | Email author" target="_blank">Ken-Li?LiEmail author Ren-Fa?Li Qing-Hua?Li |
| |
| Affiliation: | 1.School of Computer and Communication,Human University,Changsha,P.R. China;2.School of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan,P.R. China |
| |
| Abstract: | The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past
two decades, much effort has been made in order to find techniques that could lead to practical algorithms with reasonable
running time. This paper proposes a new parallel algorithm for the knapsack problem where the optimal merging algorithm is
adopted. The proposed algorithm is based on anEREW-SIMD machine with shared memory. It is proved that the proposed algorithm is both optimal and the first without memory conflicts
algorithm for the knapsack problem. The comparisons of algorithm performance show that it is an improvement over the past
researches. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
