| Optimal Parallel Algorithm for the Knapsack Problem Without Memory Conflicts |
| |
| 作者姓名： | Ken-LiLi Ren-FaLi Qing-HuaLi |
| |
| 作者单位： | [1]SchoolofComputerandCommunication,HunanUniversity,Changsha410082,P.R.China [2]SchoolofComputerScienceandTechnology,HuazhongUniversityofScienceandTechnologyWuhan430074,P.R.China |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China under Grant No.60273075，the National High Technology Development 863 Program of China under Grant No.863-306-ZD-11-01-06. |
| |
| 摘 要： | 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 an EREW-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.
|
| 关 键 词： | 渐缩问题 并行算法 最佳算法 存储冲突 |
Optimal Parallel Algorithm for the Knapsack Problem Without Memory Conflicts |
| |
| Ken-LiLi Ren-FaLi Qing-HuaLi.Optimal Parallel Algorithm for the Knapsack Problem Without Memory Conflicts[J].Journal of Computer Science and Technology,2004,19(6):0-0. |
| |
| Authors: | Ken-Li Li Ren-Fa Li Qing-Hua Li |
| |
| Affiliation: | (1) School of Computer and Communication, Human University, 410082 Changsha, P.R. China;(2) School of Computer Science and Technology, Huazhong University of Science and Technology, 430074 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 an EREW-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: | knapsack problem NP-complete parallel algorithm optimal algorithm memory conflict |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载全文 |
