Approximate MCSP (Matrix Chain Multiplication)

From Algorithm Wiki
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. 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 Scheduling Problem

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
Heejo Lee; Jong Kim; Sungje Hong; and Sunggu Lee 1997 $O(n^{2})$ $O(n^{2})$? "near optimal" Deterministic Time