Fast parallel hierarchical aggregation/disaggregation algorithms for multistage optimization problems and shortest path problems

A technique that recursively divides the original problem into a set of smaller problems which can be solved in parallel is presented. This technique is based on a hierarchical (recursive) structure of aggregation and disaggregation. For a multistage process with n stages, the present algorithm achieves a time complexity of O(log n), assuming O(1) states per stage. (Algorithms based only on the standard dynamic programming technique can achieve a time complexity no better than O(n).) The new algorithm is designed to operate on a tightly coupled parallel computer. It can serve as a fast and efficient means of decoding convolutional codes, solving routing problems in data networks, and determining minimum-fuel flight paths.

Fast parallel hierarchical aggregation/disaggregation algorithms for multistage optimization problems and shortest path problems Conference Paper