Approximate MCOP: Difference between revisions
Jump to navigation
Jump to search
(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...") |
No edit summary |
||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
$n$: number of matrices | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Latest revision as of 12:02, 15 February 2023
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