Optimal Parallel Algorithm for the Knapsack Problem Without Memory Conflicts

摘要：

The knapsack problem is very important in cryptosystem and in number theory. This paper proposes a new parallel algorithm for the knapsack problem where the method of divide and conquer is adopted. Basing on an EREW-SIMD machine with shared memory, the proposed algorithm utilizes O(2n/4) 1-ε processors, 0≤ε≤ 1, and O(2n) memory to find a solution for the n-element knapsack problem in time O(2n/4 (2n/4) ε ). Thus the cost of the proposed parallel algorithm is O(2n), which is optimal, and an improved result over the past researches.

关键词： Knapsack problem parallel algorithm optimal algorithm memory conflicts

作者: Kenli LI Qinghua LI Wang-Hui Shengyi JIANG

作者单位: School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, 430074,China National High Performance Computing Center (Wuhan), 430074,China

会议类型: 国际会议

会议名称: Proceedings of The Fourth International Conference on Parallel and Distribyted Computing,Applications and Technologies(第四届并行与分布式计算应用与技术国际会议)

会议地点: 成都

会议语种:英文

页码: 518-521

在线出版日期: 2003-08-27（万方平台首次上网日期，不代表论文的发表时间）