Optimal Parallel Algorithm for the Knapsack Problem Without Memory Conflicts

TP3; 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 parall...

Full description

Saved in:
Bibliographic Details
Published in:计算机科学技术学报（英文版） 2004-11, Vol.19 (6), p.760-768
Main Authors: Ken-Li Li, Ren-Fa Li, Qing-Hua Li
Format: Article
Language:English
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:TP3; 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 an EREW-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.
ISSN:1000-9000
DOI:10.1007/BF02973436