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 pract...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 knapsack problem - NP-complete - parallel algorithm - optimal algorithm - memory conflict 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.Ken-Li Li received his B.S. and M.S. degrees in mathematics from National University of Defense Technology and Central South University in 1995 and 2000 respectively and he is now a Ph.D. candidate in computer software and theory at Huazhong University of Science and Technology. His main research interests include parallel computing and combinatorial optimization.Ren-Fa Li received his Ph.D. degree in computer software and theory at Huazhong University of Science and Technology, and he is concurrently a professor and Ph.D. supervisor in School of Computer and Communication, Human University. His main research interests include network computing.Qing-Hua Li received his M.S. degree in computer science from Huazhong University of Science and Technology in 1981, and he is concurrently a professor and Ph.D. supervisor in School of Computer Science and Technology, Huazhong University of Science and Technology. His current research interests include parallel processing, combinatorial optimization, and grid computing.展开更多
文摘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 knapsack problem - NP-complete - parallel algorithm - optimal algorithm - memory conflict 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.Ken-Li Li received his B.S. and M.S. degrees in mathematics from National University of Defense Technology and Central South University in 1995 and 2000 respectively and he is now a Ph.D. candidate in computer software and theory at Huazhong University of Science and Technology. His main research interests include parallel computing and combinatorial optimization.Ren-Fa Li received his Ph.D. degree in computer software and theory at Huazhong University of Science and Technology, and he is concurrently a professor and Ph.D. supervisor in School of Computer and Communication, Human University. His main research interests include network computing.Qing-Hua Li received his M.S. degree in computer science from Huazhong University of Science and Technology in 1981, and he is concurrently a professor and Ph.D. supervisor in School of Computer Science and Technology, Huazhong University of Science and Technology. His current research interests include parallel processing, combinatorial optimization, and grid computing.
