Matrix Chain Scheduling Problem (Matrix Chain Multiplication)

From Algorithm Wiki
Revision as of 08:18, 10 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


The Matrix Chain Scheduling Problem (or MCSP) is an optimization problem� where the goal is to find the product sequence for evaluating a chain of matrix products and the processor schedule for the sequence such that the evaluation time is minimized on a parallel system.

Related Problems

Subproblem: Approximate MCSP

Related: Matrix Chain Ordering Problem, Approximate MCOP


$P$: number of processors

$n$: number of matrices

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Czumaj 1993 $O(log^{3} n)$ $O(n^{2})$? Exact Parallel Time