An efficient parallel Dynamic Programming Algorithm

Antonio, Tsai, and Huang proposed a scheme in 1991 to parallelize the standard dynamic programming approach to solve combinatorial multistage problems. However, their dynamic programming approach is restricted to those multistage problems where the decision made at each stage depends only on decisions made in the stage immediately preceding it. For many interesting problems the decision at each stage depends on the decisions made at all the previous stages, and therefore their approach doesn’t apply. The Matrix Chain Multiplication problem, Longest Common Subsequence problem, and Optimal Polygon Triangulation problem are some examples of such problems. The authors also present techniques for parallelizing the dynamic programming solution to such problems. The parallel algorithm they develop for a PRAM has complexity ¦](n) employing ¦](n²) processors. Since the traditional sequential algorithm for such problems is ¦](n³), the present parallel algorithm is an optimal parallel algorithm based on this traditional algorithm. They also describe the results of the present experiments that are in conformity with the theoretical complexity results. The authors also compare and contrast the result with results obtained by earlier researchers and show that the present parallel algorithm has optimal efficiency of 100% with respect to the traditional Dynamic Programming Algorithm.