Title :
Optimal parallel algorithm for the knapsack problem without memory conflicts
Author :
Kenli Li ; Qinghua Li ; Hui, Wang ; JIANG, Shengyi
Author_Institution :
Sch. of comput. Sci. & Technol., Huazhong Univ. of Sci. & Technol., Wuhan, China
Abstract :
The knapsack problem is very important in cryptosystem and in number theory. We propose 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(2n4/)1-ε processors, 0≤ε≤1, and O(2n) memory to find a solution for the n-element knapsack problem in time O(2n4/ (2n4/)ε). Thus the cost of the proposed parallel algorithm is O(2n), which is optimal, and an improved result over the past researches.
Keywords :
computational complexity; concurrency theory; cryptography; divide and conquer methods; knapsack problems; number theory; parallel algorithms; shared memory systems; EREW-SIMD machine; crypto system; divide and conquer method; knapsack problem; memory conflicts; number theory; optimal parallel algorithm; shared memory; Algorithm design and analysis; Computational modeling; Computer aided instruction; Computer science; Concurrent computing; Cost function; Cryptography; High performance computing; Parallel algorithms; Read-write memory;
Conference_Titel :
Parallel and Distributed Computing, Applications and Technologies, 2003. PDCAT'2003. Proceedings of the Fourth International Conference on
Print_ISBN :
0-7803-7840-7
DOI :
10.1109/PDCAT.2003.1236356
