Parallel Dynamic Programming Algorithms

This paper presents a number of parallel algorithms for the dynamic programming problem $$\begin{gathered}c(i,i) = 0 (0 \leqslant i \leqslant n) \hfill \\\mathop {c(i,j) = w(i,j) + \min (c(i,m - 1) + c(m,j))}\limits_{i < m \leqslant j} \hfill \\\end{gathered} $$ Sequential algorithms run in O(n3) time or, if the quadrangle inequality holds (cf. [7]), in O(n2) time. For the former we design parallel algorithms that run in O(n3/p) time on pdynamic programming problems satisfying the quadrangle inequality can be solved in O(n2/p+n log p) time using p (1systolic array for computing the c(i,j)'s that runs in linear time using p (n2) PEs.