Диссертация, Indiana University, 1994, -173 pp.
Algorithm design paradigms are particularly useful for designing new and efficient
algorithms. However, several sequential algorithm design paradigms seem to fail in
the design of efficient parallel algori thms. This dissertation focuses on the dynamic
programming paradigm, which unt il recently has only been used to design sequential
algorithms.
A graph structure is given that allows the efficient parallel solu tion of some problems
amenable to the dynamic programming paradigm. Using these graphs we show
that dynamic programming is a viable parallel algorithm design paradigm. Several
new parallel algorithms are given for two well-known optimization problems. First an
approximation algori thm is given. Then an algorithm that works by finding shortest paths in special graphs is gi ven. Finally, the last two and most efficient of these parallel
algorithms are given. These algorithms work by using new and efficient techniques
for exploiting monotonic problem constraints.
Introduction
Definitions and Foundations
Sequential Dynamic Programming
A Dynamic Graph Model
Special Dn Graphs for the MCOP
Approximating the MCOP
An O(n3) Work Polylog-Time Algorithm
An O(lg2n) Time and n Processor Algorithm
Directions of Further Research and Conclusions
Algorithm design paradigms are particularly useful for designing new and efficient
algorithms. However, several sequential algorithm design paradigms seem to fail in
the design of efficient parallel algori thms. This dissertation focuses on the dynamic
programming paradigm, which unt il recently has only been used to design sequential
algorithms.
A graph structure is given that allows the efficient parallel solu tion of some problems
amenable to the dynamic programming paradigm. Using these graphs we show
that dynamic programming is a viable parallel algorithm design paradigm. Several
new parallel algorithms are given for two well-known optimization problems. First an
approximation algori thm is given. Then an algorithm that works by finding shortest paths in special graphs is gi ven. Finally, the last two and most efficient of these parallel
algorithms are given. These algorithms work by using new and efficient techniques
for exploiting monotonic problem constraints.
Introduction
Definitions and Foundations
Sequential Dynamic Programming
A Dynamic Graph Model
Special Dn Graphs for the MCOP
Approximating the MCOP
An O(n3) Work Polylog-Time Algorithm
An O(lg2n) Time and n Processor Algorithm
Directions of Further Research and Conclusions