| The Knuth-Yao Quadrangle-Inequality Speedup is a Consequence of Total-Monotonicity ∗ (2009) | |||||||||||||||
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 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 3) down to O(n 2), 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 the right of the current nodes at each step) in O(n) time per step. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||