Approximate MCOP (Matrix Chain Multiplication)
Revision as of 10:17, 15 February 2023 by Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Approximate MCOP (Matrix Chain Multiplication)}} == 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. == R...")
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