# 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