Title: The Quadrangle-Inequality Dynamic-Programming Speedup is a Consequence of
Totally Monotonicity


Speaker: Zhang Yan
HKUST

Date: Friday Sept 30, 2005
Time 11-12 Venue: Room 3464, HKUST   


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 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  symptotically as
fast as the best previously known static ones.

This is joint work with Wolf Bein,  Mordecai Golin and Larry Larmore