English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

The product of a matrix chain consisting of $n$ matrices can be computed in$C_{n-1}$ (Catalan's number) different ways, each identified by a distinctparenthesisation of the chain. The best algorithm to select a parenthesisationthat minimises the cost runs in $O(n \log n)$ time. Approximate algorithms runin $O(n)$ time and find solutions that are guaranteed to be within a certainfactor from optimal; the best factor is currently $1.155$. In this article, wefirst prove two results that characterise different parenthesisations, and thenuse those results to improve on the best known approximation algorithms.Specifically, we show that (a) each parenthesisation is optimal somewhere inthe problem domain, and (b) exactly $n + 1$ parenthesisations are essential inthe sense that the removal of any one of them causes an unbounded penalty foran infinite number of problem instances. By focusing on essentialparenthesisations, we improve on the best known approximation algorithm andshow that the approximation factor is at most $1.143$.

On the Parenthesisations of Matrix Chains: All are Useful, Few Are Essential