Optimization and Performance Analysis of Parallel Dynamic Programming Algorithm for Knapsack Problem
We study a parallel dynamic programming algorithm for Knapsack problem based on block decomposition. Two cases are considered: processors can store intermediate results of previous computations and intermediate results should be communicated to each processor. The former corresponds to classical cluster architecture while the latter is tailored to grid computing. For both cases we state a scheduling problem of minimizing the total complete time. We suggest a fast algorithm to solve this problem and present results of simulation and real experiments confirming the algorithm`s efficiency.