The two list algorithm for the knapsack problem on an FPS T20 (Q1118989): Difference between revisions

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.