Matrix Chain Scheduling Problem: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
(Created page with "{{DISPLAYTITLE:Matrix Chain Scheduling Problem (Matrix Chain Multiplication)}} == Description == 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 == Generalizations: Matrix Chain Ordering Problem Subproblem: Approximat...")
 
No edit summary
Line 14: Line 14:
== Parameters ==  
== Parameters ==  


<pre>$P$: number of processors
$P$: number of processors
$n$: number of matrices</pre>
 
$n$: number of matrices


== Table of Algorithms ==  
== Table of Algorithms ==  

Revision as of 13:02, 15 February 2023

Description

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

Generalizations: Matrix Chain Ordering Problem

Subproblem: Approximate MCSP

Related: Approximate MCOP

Parameters

$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

References/Citation

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

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