0-1 Knapsack Problem: BSP/CGM Algorithm and Implementation

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