首页|期刊导航|西南交通大学学报（英文版）|Improved Parallel Three-List Algorithm for the Knapsack Problem without Memory Conflicts
西南交通大学学报（英文版）2006，Vol.14Issue(1)：7-14,8.
Improved Parallel Three-List Algorithm for the Knapsack Problem without Memory Conflicts
Improved Parallel Three-List Algorithm for the Knapsack Problem without Memory Conflicts
摘要
Abstract
Based on the two-list algorithm and the parallel three-list algorithm, an improved parallel three-list algorithm for knapsack problem is proposed, in which the method of divide and conquer, and parallel merging without memory conflicts are adopted. To find a solution for the n-element knapsack problem, the proposed algorithm needs O(23n/8) time when O(23n/8) shared memory units and O(2n/4) processors are available. The comparisons between the proposed algorithm and 10 existing algorithms show that the improved parallel three-list algorithm is the first exclusive-read exclusive-write (EREW) parallel algorithm that can solve the knapsack instances in less than O(2n/2) time when the available hardware resource is smaller than O(2n/2), and hence is an improved result over the past researches.关键词
Knapsack problem/NP-Hard/Parallel algorithm/Memory conflicts/Hardware-time tradeoffKey words
Knapsack problem/NP-Hard/Parallel algorithm/Memory conflicts/Hardware-time tradeoff分类
数理科学引用本文复制引用
Pan Jun,Li Kenli,Li Qinghua..Improved Parallel Three-List Algorithm for the Knapsack Problem without Memory Conflicts[J].西南交通大学学报（英文版）,2006,14(1):7-14,8.基金项目
The National Natural Science Foundation of China (No.60273075), and the National High Technique Development Program (No.863-306 ZD-11-01-06) （No.60273075）
