The Knuth-Yao quadrangle-inequality speedup is a consequence of total-monotonicity

ABSTRACT

There exist several general techniques in the literature for speeding up naive implementations of dynamic programming. Two of the best known are the Knuth-Yao quadrangle inequality speedup and the SMAWK algorithm for finding the row-minima of totally monotone matrices. Although both of these techniques use a quadrangle inequality and seem similar they are actually quite different and have been used differently in the literature.In this paper we show that the Knuth-Yao technique is actually a direct consequence of total monotonicity. As well as providing new derivations of the Knuth-Yao result, this also permits showing how to solve the Knuth-Yao problem directly using the SMAWK algorithm. Another consequence of this approach is a method for solving online versions of problems with the Knuth-Yao property. The online algorithms given here are asymptotically as fast as the best previously known static ones. For example the Knuth-Yao technique speeds up the standard dynamic program for finding the optimal binary search tree of n elements from Θ(n³) down to O(n²), and the results in this paper allow construction of an optimal binary search tree in an online fashion (adding a node to the left or right of the current nodes at each step) in O(n) time per step.We conclude by discussing how the general technique described here is also applicable to later extensions of the Knuth-Yao result, such as those developed by Borchers and Gupta.

REFERENCES

• 1: Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter W. Shor, and Robert E. Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2:195--208, 1987.
• 2: Alok Aggarwal and James Park. Notes on searching in multidimensional monotone arrays. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 497--512, 1988.
• 3: M. J. Atallah , S. R. Kosaraju , L. L. Larmore , G. L. Miller , S.-H. Teng, Constructing trees in parallel, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.421-431, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72980]
• 4: Amotz Bar-Noy , Richard E. Ladner, Efficient Algorithms for Optimal Stream Merging for Media-on-Demand, SIAM Journal on Computing, v.33 n.5, p.1011-1034, 2004 [doi>10.1137/S0097539701389245]
• 5: Al Borchers , Prosenjit Gupta, Extending the quadrangle inequality to speed-up dynamic programming, Information Processing Letters, v.49 n.6, p.287-290, March 22, 1994 [doi>10.1016/0020-0190(94)90101-5]
• 6: Rainer E. Burkard , Bettina Klinz , Rüdiger Rudolf, Perspectives of Monge properties in optimization, Discrete Applied Mathematics, v.70 n.2, p.95-161, Sept. 24, 1996 [doi>10.1016/0166-218X(95)00103-X]
• 7: Zvi Galil , Kunsoo Park, Dynamic programming with convexity, concavity and sparsity, Theoretical Computer Science, v.92 n.1, p.49-76, Jan. 6, 1992 [doi>10.1016/0304-3975(92)90135-3]
• 8: E. N. Gilbert and E. F. Moore. Variable length encodings. Bell System Technical Journal, 38:933--967, 1959.
• 9: Donald E. Knuth. Optimum binary search trees. Acta Informatica, 1:14--25, 1971.
• 10: Lawrence L. Larmore , Baruch Schieber, On-line dynamic programming with applications to the prediction of RNA secondary structure, Journal of Algorithms, v.12 n.3, p.490-515, Sept. 1991 [doi>10.1016/0196-6774(91)90016-R]
• 11: Sailesh K. Rao, P. Sadayappan, Frank K. Hwang, and Peter W. Shor. The rectilinear steiner arborescence problem. Algorithmica, 7(2-3):277--288, 1992.
• 12: Amir Said, Efficient Alphabet Partitioning Algorithms for Low-Complexity Entropy Coding, Proceedings of the Data Compression Conference, p.183-192, March 29-31, 2005 [doi>10.1109/DCC.2005.35]
• 13: Russell L. Wessner. Optimal alphabetic search trees with restricted maximal height. Information Processing Letters, 4(4):90--94, 1976.
• 14: Robert Wilber, The concave least-weight subsequence problem revisited, Journal of Algorithms, v.9 n.3, p.418-425, September 1988 [doi>10.1016/0196-6774(88)90032-6]
• 15: F. Frances Yao, Efficient dynamic programming using quadrangle inequalities, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.429-435, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804691]
• 16: F. Frances Yao. Speed-up in dynamic programming. SIAM Journal on Matrix Analysis and Applications (formerly SIAM Journal on Algebraic and Discrete Methods), 3(4):532--540, 1982.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

General Terms:
Algorithms, Theory