EFFICIENT ALGORITHMS FOR A CLASS OF PARTITIONING PROBLEMS

We address the problem of optimally partitioning the modules of chain- or tree-like tasks over chain-structured or host-satellite multiple c omputer systems. This important class of problems includes many signal processing and industrial control applications. Prior research has re sulted in a succession of faster exact and approximate algorithms for these problems. We describe polynomial exact and approximate algorithm s for this class that are better than any of the previously reported a lgorithms. Our approach is based on a preprocessing step that condense s the given chain or tree structured task into a monotonic chain or tr ee. The partitioning of this monotonic task can then be carried out us ing fast search techniques.