An Optimal Parallel Algorithm for the Knapsack Problem Based on EREW

作     者：李肯立 蒋盛益 王卉 李庆华 

作者机构：School of Computer Science and TechnologyHuazhong University of Science and Technology 

出 版 物：《Journal of Southwest Jiaotong University(English Edition)》 (西南交通大学学报（英文版）)

年 卷 期：2003年第11卷第2期

页      面：131-137页

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：SupportedbytheNaturalScienceFoundationofChina (No .60 2 730 75 )andtheNationalHighTechniqueDevelopmentProgram ( 863 30 6ZD 1 1 0 1 0 6) 

主　　题：knapsack problem NP-complete parallel algorithm divide and conquer 

摘      要：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(2 n/4 ) 1-ε processors, 0≤ ε ≤1, and O(2 n/2 ) memory to find a solution for the n -element knapsack problem in time O(2 n/4 (2 n/4 ) ε) . The cost of the proposed parallel algorithm is O(2 n/2 ) , which is an optimal method for solving the knapsack problem without memory conflicts and an improved result over the past researches.