Editing Matrix chain multiplication (section)

=== Chin-Hu-Shing approximate solution ===
An algorithm created independently by Chin<ref>{{cite journal |last1=Chin |first1=Francis Y.|author1-link=Francis Y. L. Chin |title=An O(n) algorithm for determining a near-optimal computation order of matrix chain products |journal=Communications of the ACM |date=July 1978 |volume=21 |issue=7 |pages=544–549 |doi=10.1145/359545.359556|doi-access=free}}</ref> and Hu & Shing<ref>{{cite journal |last1=Hu |first1=T.C |last2=Shing |first2=M.T |title=An O(n) algorithm to find a near-optimum partition of a convex polygon |journal=Journal of Algorithms |date=June 1981 |volume=2 |issue=2 |pages=122–138 |doi=10.1016/0196-6774(81)90014-6}}</ref> runs in O(''n'') and produces a parenthesization which is at most 15.47% worse than the optimal choice. In most cases the algorithm yields the optimal solution or a solution which is only 1-2 percent worse than the optimal one.<ref name="Czumaj" />

The algorithm starts by translating the problem to the polygon partitioning problem. To each vertex ''V'' of the polygon is associated a weight ''w''. Suppose we have three consecutive vertices <math>V_{i-1}, V_i, V_{i+1}</math>, and that <math>V_{\min}</math> is the vertex with minimum weight <math>w_{\min}</math>.
We look at the quadrilateral with vertices <math>V_{\min}, V_{i-1}, V_i, V_{i+1}</math> (in clockwise order).
We can triangulate it in two ways:
*<math>(V_{\min}, V_{i-1}, V_i)</math> and <math>(V_{\min}, V_{i+1}, V_i)</math>, with cost <math>w_{\min}w_{i-1}w_i+w_{\min}w_{i+1}w_i</math>
*<math>(V_{\min}, V_{i-1}, V_{i+1})</math> and <math>(V_{i-1}, V_i, V_{i+1})</math> with cost <math>w_{\min}w_{i-1}w_{i+1}+w_{i-1}w_{i}w_{i+1}</math>.

Therefore, if

: <math>w_{\min}w_{i-1}w_{i+1}+w_{i-1}w_{i}w_{i+1}<w_{\min}w_{i-1}w_i+w_{\min}w_{i+1}w_i </math>

or equivalently

: <math>\frac{1}{w_i}+\frac{1}{w_{\min}}<\frac{1}{w_{i+1}}+\frac{1}{w_{i-1}} </math>

we remove the vertex <math>V_i</math> from the polygon and add the side <math>(V_{i-1}, V_{i+1})</math> to the triangulation.
We repeat this process until no <math>V_i</math> satisfies the condition above.
For all the remaining vertices <math>V_n</math>, we add the side <math>(V_{\min}, V_n)</math> to the triangulation. 
This gives us a nearly optimal triangulation.