VERY FAST APPROXIMATION OF THE MATRIX CHAIN PRODUCT PROBLEM

This paper considers the matrix chain product problem. This problem ca n be solved in O(n log n) sequential time, while the best known parall el NC algorithm runs in O(log(2)n) time using n(6)/log(6)n processors and in O(log(3)n) time with O(n(2)) time-processor product. This paper presents a very fast parallel algorithm for approximately solving the matrix chain product problem and for the problem for finding a near-o ptimal triangulation of a convex polygon. It runs in O(log n) time on a CREW PRAM and in O(log log n) time on a COMMON CRCW PRAM. If the dim ensions of matrices are integers drawn from a domain [k,..., k + s], w e can speed up our algorithm to run in O(log log log(n + s)) time on a COR?MON CRCW PRAM. In all cases the total time-processor product is l inear. The algorithm produces solutions for the above problems that ar e at most 1/(2 root 3 + 3) (approximate to 0.1547) times the optimal s olutions. (C) 1996 Academic Press, Inc.