Approximate MCOP (Matrix Chain Multiplication)
Jump to navigation
Jump to search
Description
Matrix chain multiplication (or Matrix Chain Ordering Problem; MCOP) is an optimization problem. Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices. In the approximation problem, the matrix multiplication carried out with the output result will use a number of operations that has some sort of upper bound based on the optimal solution.
Related Problems
Generalizations: Matrix Chain Ordering Problem
Related: Matrix Chain Scheduling Problem, Approximate MCSP
Parameters
$n$: number of matrices
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Czumaj | 1996 | $O(\log n)$ | $O(n)$ | 1.1547 | Parallel | Time |
| Czumaj | 1996 | $O(\log \log n)$ | $O(n)$ | 1.1547 | Parallel | Time |
| Chandra | 1975 | $O(n)$ | $O(n)$? | 2 | Deterministic | Time |
| Chin | 1978 | $O(n)$ | $O(n)$ | 1.2485 | Deterministic | Time |
| Prakesh Ramanan | 1996 | $O(log^{4} n)$ | $O(n)$? | Exact | Parallel | Time |
References/Citation
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.218.8168&rep=rep1&type=pdf