Friday Jan 27, 2006 12:30pm-1:20pm in CSE 403

TITLE: The Quadrangle-Inequality Dynamic-Programming Speedup is a Consequence of Total Monotonicity

Speaker: Mordecai Golin, Hong Kong UST

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

This is joint work with Wolf Bein, Larry Larmore and Yan Zhang