| An Optimal Parallel Algorithm for the Knapsack Problem Based on EREW |
| |
| 作者姓名： | 李肯立 蒋盛益 王卉 李庆华 |
| |
| 作者单位： | School of Computer Science and Technology，Huazhong University of Science and Technology，School of Computer Science and Technology，Huazhong University of Science and Technology，School of Computer Science and Technology，Huazhong University of Science and Technology，School of Computer Science and Technology，Huazhong University of Science and Technology Wuhan 430074，China，Wuhan 430074，China，Wuhan 430074，China，Wuhan 430074，China |
| |
| 基金项目： | 国家自然科学基金，国家高技术研究发展计划(863计划) |
| |
| 摘 要： | IntroductionGivenn positiveintegersW =(w1,w2 ,… ,wn)andapositiveintegerM ,theknapsack problem (alsocalledthesubsetsum problembysomeauthors)isthedecisionproblemoffindingasetI {1 ,2 ,… ,n},suchthat∑i∈I=M ,i∈I .ThisproblemwasprovedtobeNP complete1] ;i
|
| 关 键 词： | 平行运算 背包问题 EREW-SIMD模型 内存冲突 算法理论 |
An Optimal Parallel Algorithm for the Knapsack Problem Based on EREW |
| |
| Li Kenli Jiang Shengyi Wang Hui Li Qinghua.An Optimal Parallel Algorithm for the Knapsack Problem Based on EREW[J].Journal of Southwest Jiaotong University,2003,11(2):131-137. |
| |
| Authors: | Li Kenli Jiang Shengyi Wang Hui Li Qinghua |
| |
| Abstract: | A new parallel algorithm is proposed for the knapsack problem where the method of divide and conquer is adopted. Based on an EREW-SIMD machine with shared memory, the proposed algorithm utilizes O(2n/4)1-ε processors, 0≤ε≤1, and O(2n/2) memory to find a solution for the n-element knapsack problem in time O(2n/4(2n/4)ε). The cost of the proposed parallel algorithm is O(2n/2), which is an optimal method for solving the knapsack problem without memory conflicts and an improved result over the past researches. |
| |
| Keywords: | knapsack problem NP-complete parallel algorithm divide and conquer |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
