{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T16:52:25Z","timestamp":1771951945193,"version":"3.50.1"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,4,1]],"date-time":"2025-04-01T00:00:00Z","timestamp":1743465600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,4,14]],"date-time":"2025-04-14T00:00:00Z","timestamp":1744588800000},"content-version":"vor","delay-in-days":13,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Umea University"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2025,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The product of a matrix chain consisting of <jats:italic>n<\/jats:italic> matrices can be computed in <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$C_{n-1}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>C<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>-<\/mml:mo>\n                      <mml:mn>1<\/mml:mn>\n                    <\/mml:mrow>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> (Catalan\u2019s number) different ways, each identified by a distinct parenthesisation of the chain. The best algorithm to select a parenthesisation that minimises the cost runs in <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(n \\log n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> time. Approximate algorithms run in <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>) time and find solutions that are guaranteed to be within a certain factor from optimal; the best factor is currently 1.155. In this article, we first prove two results that characterise different parenthesisations, and then use those results to improve on the best known approximation algorithms. Specifically, we show that (a) each parenthesisation is optimal somewhere in the problem domain, and (b) exactly <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$n + 1$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> parenthesisations are essential in the sense that the removal of any one of them causes an unbounded penalty for an infinite number of problem instances. By focusing on essential parenthesisations, we improve on the best known approximation algorithm and show that the approximation factor is at most 1.143.<\/jats:p>","DOI":"10.1007\/s10878-025-01290-7","type":"journal-article","created":{"date-parts":[[2025,4,14]],"date-time":"2025-04-14T18:40:06Z","timestamp":1744656006000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the parenthesisations of matrix chains: All are useful, few are essential"],"prefix":"10.1007","volume":"49","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6406-0526","authenticated-orcid":false,"given":"Francisco","family":"L\u00f3pez","sequence":"first","affiliation":[]},{"given":"Lars","family":"Karlsson","sequence":"additional","affiliation":[]},{"given":"Paolo","family":"Bientinesi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,4,14]]},"reference":[{"key":"1290_CR1","doi-asserted-by":"crossref","unstructured":"Barthels H, Copik M, Bientinesi P (2018) The generalized matrix chain algorithm. In: Proceedings of the 2018 international symposium on code generation and optimization, pp. 138\u2013148. ACM,","DOI":"10.1145\/3168804"},{"issue":"3","key":"1290_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3446632","volume":"47","author":"Henrik Barthels","year":"2021","unstructured":"Barthels Henrik, Psarras Christos, Bientinesi Paolo (2021) Linnea: Automatic generation of efficient linear algebra programs. ACM Trans Math Softw 47(3):1\u201326","journal-title":"ACM Trans Math Softw"},{"key":"1290_CR3","unstructured":"Chandra AK (1975) Computing matrix chain products in near-optimal time. Technical Report RC-5625 (#24393), IBM Thomas J. Watson Research Center, P. O. Box 218, Yorktown Heights, New York, USA,"},{"issue":"7","key":"1290_CR4","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1145\/359545.359556","volume":"21","author":"FY Chin","year":"1978","unstructured":"Chin FY (1978) An O(n) algorithm for determining a near-optimal computation order of matrix chain products. Commun ACM 21(7):544\u2013549","journal-title":"Commun ACM"},{"issue":"9","key":"1290_CR5","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1109\/TC.1973.5009182","volume":"100","author":"SS Godbole","year":"1973","unstructured":"Godbole SS (1973) On efficient computation of matrix chain products. IEEE Trans Comput 100(9):864\u2013866","journal-title":"IEEE Trans Comput"},{"issue":"2","key":"1290_CR6","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/0196-6774(81)90014-6","volume":"2","author":"TC Hu","year":"1981","unstructured":"Hu TC, Shing MT (1981) An O(n) algorithm to find a near-optimum partition of a convex polygon. J Algo 2(2):122\u2013138","journal-title":"J Algo"},{"issue":"2","key":"1290_CR7","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1137\/0211028","volume":"11","author":"TC Hu","year":"1982","unstructured":"Hu TC, Shing MT (1982) Computation of matrix chain products. Part I. SIAM J Comput 11(2):362\u2013373","journal-title":"Part I. SIAM J Comput"},{"issue":"2","key":"1290_CR8","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1137\/0213017","volume":"13","author":"TC Hu","year":"1984","unstructured":"Hu TC, Shing MT (1984) Computation of matrix chain products. Part II. SIAM J Comput 13(2):228\u2013251","journal-title":"Part II. SIAM J Comput"},{"issue":"4","key":"1290_CR9","doi-asserted-by":"publisher","first-page":"834","DOI":"10.1137\/S0097539790190077","volume":"23","author":"Prakash Ramanan","year":"1994","unstructured":"Ramanan Prakash (1994) A new lower bound technique and its application: Tight lower bound for a polygon triangulation problem. SIAM J Comput 23(4):834\u2013851. https:\/\/doi.org\/10.1137\/S0097539790190077","journal-title":"SIAM J Comput"},{"issue":"5","key":"1290_CR10","doi-asserted-by":"publisher","first-page":"1481","DOI":"10.1137\/18M1195401","volume":"48","author":"Oded Schwartz","year":"2019","unstructured":"Schwartz Oded, Weiss Elad (2019) Revisiting computation of matrix chain products. SIAM J Comput 48(5):1481\u20131486","journal-title":"SIAM J Comput"},{"key":"1290_CR11","doi-asserted-by":"publisher","unstructured":"Siek JG, Karlin I, Jessup ER (2008) . Build to order linear algebra kernels. In 2008 IEEE international symposium on parallel and distributed processing, pp. 1\u20138, https:\/\/doi.org\/10.1109\/IPDPS.2008.4536183","DOI":"10.1109\/IPDPS.2008.4536183"},{"key":"1290_CR12","doi-asserted-by":"crossref","unstructured":"Spampinato DG, Fabregat-Traver D, Bientinesi P, P\u00fcschel M (2018) Program generation for small-scale linear algebra applications. In: International symposium on code generation and optimization (CGO), pp. 327\u2013339","DOI":"10.1145\/3168812"},{"issue":"4","key":"1290_CR13","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1137\/0603055","volume":"3","author":"FF Yao","year":"1982","unstructured":"Yao FF (1982) Speed-up in dynamic programming. SIAM J Algeb Discr Methods 3(4):532\u2013540","journal-title":"SIAM J Algeb Discr Methods"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01290-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-025-01290-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01290-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,22]],"date-time":"2025-04-22T07:55:48Z","timestamp":1745308548000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-025-01290-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4]]},"references-count":13,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["1290"],"URL":"https:\/\/doi.org\/10.1007\/s10878-025-01290-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4]]},"assertion":[{"value":"24 March 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 April 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors declare they have no financial interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"52"}}