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.

Language

english

UNLV article access

Share

COinS