2021/04/05 by Thong Le, Dan Gusfield, Le, Thong +1
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2104.01777
openalex publication_date 2021/04/05 · openalex created_date 2021/04/13 · openalex updated_date 2026/07/28
The \it matrix-chain multiplication problem is a classic problem that is widely taught to illustrate dynamic programming. The textbook solution runs in θ(n3) time. However, there is a complex O(n log n)-time method \citeHU82, based on triangulating convex polygons, and a description without proofs or implementation detail, of a much simpler O(n2)-time method \citeYAO82. There is also a linear-time approximation algorithm with a small worst-case error bound \citeHU-SHING1981. In this paper, we make five contributions both to theory and pedagogy: 1) We simplify the approach in \citeYAO82, and provide complete, correct proofs and implementation details, to establish the O(n2)-time bound. We believe that this exposition is simple enough for classroom use. 2) We extend the O(n2)-time bound to a natural class of polygon-triangulation problems that generalizes the original polygon-triangulation problem in \citeHU82. 3) We show that the worst-case running time of the method in \citeYAO82, and of our version, is Θ(n2). 4) We show that in a natural variant of the original polygon-triangulation problem, the approximation method of \citeHU-SHING1981 does not achieve the same error bound, but does achieve an error bound about twice the original bound. 5) We detail empirical testing, showing that on random data our variant runs in Θ(n log n) time, while the approach in \citeYAO82 empirically takes Θ(n2) time. Software for these tests is posted on the web.