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
Talk
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 1 August 2005
13:30
45 Minutes
46.1 - MPII
024
Saarbrücken
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 asymptotically as fast as the best previously known static ones.
Contact
Yan Zhang
121
--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.
Yan Zhang, 07/26/2005 15:47 -- Created document.