Campus Event Calendar

Event Entry

What and Who

Quadrangle Inequality Dynamic Programming Speedup is a Consequence of Totally Monotonicity

Yan Zhang
Max-Planck-Institut für Informatik - AG 1
AG 1, AG 2, AG 3, AG 4, AG 5  
AG Audience

Date, Time and Location

Monday, 1 August 2005
45 Minutes
46.1 - MPII


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 talk 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.


Yan Zhang
--email hidden
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

Dynamic Programming; Quadrangle Inequality; Totally Monotone Matrix; Optimal Binary Search Tree

Yan Zhang, 07/31/2005 23:07
Yan Zhang, 07/26/2005 15:47 -- Created document.