View source for Approximate MCOP

{{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.

== Related Problems == 

Generalizations: [[Matrix Chain Ordering Problem]]

Related: [[Matrix Chain Scheduling Problem]], [[Approximate MCSP]]

== Parameters == 

$n$: number of matrices

== Table of Algorithms == 

{| class="wikitable sortable"  style="text-align:center;" width="100%"

! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference

|-

| [[Czumaj (Approximate MCOP Matrix Chain Multiplication)|Czumaj]] || 1996 || $O(\log n)$ || $O(n)$ || 1.1547 || Parallel || [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.218.8168&rep=rep1&type=pdf Time]
|-
| [[Czumaj (Approximate MCOP Matrix Chain Multiplication)|Czumaj]] || 1996 || $O(\log \log n)$ || $O(n)$ || 1.1547 || Parallel || [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.218.8168&rep=rep1&type=pdf Time]
|-
| [[Chandra (Approximate MCOP Matrix Chain Multiplication)|Chandra]] || 1975 || $O(n)$ || $O(n)$? || 2 || Deterministic || [https://www.worldcat.org/title/computing-matrix-chain-products-in-near-optimal-time/oclc/727708286 Time]
|-
| [[Chin (Approximate MCOP Matrix Chain Multiplication)|Chin]] || 1978 || $O(n)$ || $O(n)$ || 1.2485 || Deterministic || [https://dl.acm.org/citation.cfm?id=359556 Time]
|-
| [[Prakesh Ramanan (Approximate MCOP Matrix Chain Multiplication)|Prakesh Ramanan]] || 1996 || $O(log^{4} n)$ || $O(n)$? || Exact || Parallel || [https://epubs.siam.org/doi/abs/10.1137/0225039 Time]
|-
|}

== References/Citation == 

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.218.8168&rep=rep1&type=pdf