E.N. Cáceres and C. Nishibe (Brazil)
0-1 Knapsack, BSP/CGM Algorithms, Parallel Algorithms, MPI
We present a new BSP/CGM parallel algorithm for the 0-1 Knapsack Problem. Given n different items and a knap sack of capacity W, our algorithm solves the 0-1 Knapsack Problem using O(nW p ) local computation time with O(p) communication rounds. Using Dynamic Programming, our algorithm solves locally pieces of the Knapsack Problem in each processor and uses a wavefront approach in order to solve the whole problem. Our algorithm was implemented in a Beowulf and the obtained times showed good speed-up and scalability.
Important Links:
Go Back
