The two list algorithm for the knapsack problem on an FPS T20 (Q1118989)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The two list algorithm for the knapsack problem on an FPS T20 |
scientific article |
Statements
The two list algorithm for the knapsack problem on an FPS T20 (English)
0 references
1989
0 references
The paper deals with a parallel implementation of the traditional two- list algorithm for the knapsack problem: given positive integers \(w_ 1,w_ 2,...,w_ n\) and M, find a subset L of \(\{\) 1,2,...,n\(\}\) such that \(w_ i=M\) where i's range over L. The current attempt aims at parallelizing by dividing the solution domain. Suppose there are \(2^ q\) processors labelled \(0,1,...,2^ q-1\) such that label j has \(R_ j\) as binary representation. A processor j works with \(W=(w_{q+1},...,w_ n)\) and \(M=M-\sum r_ kw_ r,\) \(1\leq k\leq i\). If a solution \(C_ j\) is found, then the final solution is the concatenation of \(R_ j\) and \(C_ j\). This parallelization yields a maximum speedup of \(2^{q/2}\). The algorithm was implemented on FPS T20 parallel machines (16 processors) coupled with hypercube topology, using OCCAM language.
0 references
parallel computation
0 references
NP-complete
0 references
parallel algorithms
0 references
exponential complexity
0 references
Branch and bound algorithms
0 references
two-list algorithm
0 references
knapsack problem
0 references
hypercube
0 references