2026-08-11T08:10:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14446 2024-03-06T10:54:01Z ddc:004 open_access

An Approximation Algorithm for the Matrix Tree Multiplication Problem Abo-Khamis, Mahmoud Curtin, Ryan Im, Sungjin Moseley, Benjamin Ngo, Hung Pruhs, Kirk Samadian, Alireza Matrix Multiplication Approximation Algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mahmoud Abo-Khamis and Ryan Curtin and Sungjin Im and Benjamin Moseley and Hung Ngo and Kirk Pruhs and Alireza Samadian 2021 Is Part Of LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2021.6 urn:nbn:de:0030-drops-144464 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.6 eng https://creativecommons.org/licenses/by/4.0/legalcode