Approximate MCOP (Matrix Chain Multiplication)

From Algorithm Wiki
Revision as of 12:02, 15 February 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


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


$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