Title :
A Parallel Algorithm by Sampling for the Knapsack Problem Based on MIMD Parallel Computers
Author :
Liu, Xiao-ling ; Gao, Shou-ping ; Gong, De-liang ; Ken-Li Li
Author_Institution :
Dept. of Comput. Sci., Xiangnan Coll., Chenzhou
Abstract :
The knapsack problem is a famous NP-complete problem. It is very important in the research on cryptosystem and number theory. After its proposed parallel algorithms are analyzed deeply, a new parallel algorithm by sampling is proposed based on MIMD supercomputers in the paper. Then performance analysis and comparisons are illuminated. Finally the experimental results of the knapsack instances randomly generated on IBM P690 supercomputer are given. The results show: the parallel efficiency can be over 60% when solving the larger scale knapsack instances (n ges 40). Thus it is proved that the proposed parallel algorithm for the knapsack problem is feasible and efficient on MIMD scalable supercomputers
Keywords :
computational complexity; knapsack problems; parallel algorithms; sampling methods; MIMD parallel computers; NP-complete problem; knapsack problem; parallel algorithm; sampling; Algorithm design and analysis; Clustering algorithms; Computer science; Concurrent computing; Cryptography; Educational institutions; Parallel algorithms; Performance analysis; Sampling methods; Supercomputers;
Conference_Titel :
Parallel and Distributed Computing, Applications and Technologies, 2006. PDCAT '06. Seventh International Conference on
Conference_Location :
Taipei
Print_ISBN :
0-7695-2736-1
DOI :
10.1109/PDCAT.2006.14
