The Knuth-Yao Quadrangle-inequality Speedup is a Consequence of Total-monotonicity
Document Type
Conference Proceeding
Publication Date
12-1-2009
Publication Title
ACM Transactions on Algorithms (TALG)
Volume
6
Issue
1
First page number:
31
Last page number:
40
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 article 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 Θ(n3) down to O(n2), and the results in this article 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.
File Format
File Size
321 kb
Language
english
Repository Citation
Bein, W.,
Golin, M. J.,
Larmore, L. L.,
Zhang, Y.
(2009).
The Knuth-Yao Quadrangle-inequality Speedup is a Consequence of Total-monotonicity.
ACM Transactions on Algorithms (TALG), 6(1),
31-40.
http://dx.doi.org/10.1145/1644015.1644032
