Paper Info
Title
A parallel algorithm for the knapsack problem using a generation and searching technique
Abstract
The purpose of this paper is to propose a new parallel algorithm for the knapsack problem. We develop a generation and searching technique to derive the desired two ordered lists in the preliminary process of the general knapsack problem. The proposed parallel algorithm is developed on the basis of an SIMD machine with shared memory. The algorithm needs O (2 n 4 ) memory and O (2 n 8 ) processors to find a solution for the knapsack problem of n components in time O (2 n 2 ) . The proposed parallel algorithm has a cost of O (2 5n 8 ) which is an improved result over the past researches.
Year
DOI
Venue
1994
10.1016/0167-8191(94)90083-3
Parallel Computing
Keywords
Field
DocType
knapsack problem,parallel algorithm,shared memory multiprocessor,simd machine,performance analysis
Shared memory,Parallel algorithm,Computer science,Parallel computing,SIMD,Simd computer,Theoretical computer science,Knapsack problem,Shared memory multiprocessor
Journal
Volume
Issue
ISSN
20
2
Parallel Computing
Citations 
PageRank 
References 
11
0.92
11
Authors
3
Name
Order
Citations
PageRank
Henry Ker-Chang Chang16816.25
Jonathan Jen-rong Chen2122.29
Shyong-Jian Shyu3604.47