An Approximation Algorithm for the Matrix Tree Multiplication Problem
An Approximation Algorithm for the Matrix Tree Multiplication Problem
复制标题
DOI：
10.4230/lipics.mfcs.2021.6
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Mahmoud Abo Khamis;Ryan R. Curtin;Sungjin Im;Benjamin Moseley;H. Ngo;K. Pruhs;Alireza Samadian
中科院分区：
文献类型：
--
作者：
Mahmoud Abo Khamis;Ryan R. Curtin;Sungjin Im;Benjamin Moseley;H. Ngo;K. Pruhs;Alireza Samadian
我们考虑矩阵树乘法问题。这个问题是对许多入门算法教科书的动态编程章节中涵盖的经典矩阵链乘问题的概括。矩阵树乘法问题的实例由一个扎根树组成，该树具有与每个边缘关联的矩阵。对于树上的每个叶子，输出是从根到该叶子的链/路径上的矩阵的产物。在各个链之间共享的矩阵乘积只需要一次计算一次，可能在不同的根部到叶子链之间共享。通过执行的标量乘法数量评估算法。我们的主要结果是一种线性时间算法，其执行标量乘法数的数量最多是标量乘法的最佳数量
We consider the Matrix Tree Multiplication problem. This problem is a generalization of the classic Matrix Chain Multiplication problem covered in the dynamic programming chapter of many introductory algorithms textbooks. An instance of the Matrix Tree Multiplication problem consists of a rooted tree with a matrix associated with each edge. The output is, for each leaf in the tree, the product of the matrices on the chain/path from the root to that leaf. Matrix multiplications that are shared between various chains need only be computed once, potentially being shared between different root to leaf chains. Algorithms are evaluated by the number of scalar multiplications performed. Our main result is a linear time algorithm for which the number of scalar multiplications performed is at most 15 times the optimal number of scalar multiplications