Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/27745

The Knuth-Yao Quadrangle-Inequality Speedup is a Consequence of Total Monotonicity

Authors Bein, Wolfgang
Golin, Mordecai J. View this author's profile
Larmore, Lawrence L.
Zhang, Yan
Issue Date 2009
Source ACM transactions on algorithms , v. 6, (1), 2009, DEC
Summary 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 Theta(n(3)) down to O(n(2)), 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.
Subjects
ISSN 1549-6325
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Find@HKUST