Title: Revisiting The Monge Property 
Speaker:  Mordecai Golin
HKUST

Date: Friday, November 7, 2007
Time 11-12PM
Venue: Room 3464, HKUST

 
Abstract:
We revisit the "Monge" speedup for dynamic programming and show that 
not only time, but in many cases also space, can be reduced by an order 
of magnitude. We further show that it's often possible to maintain the 
speedup in an online setting (the original Monge speedup assumed static input). 

(joint work with Amotz Bar-Noy, Yi Feng, Larry Larmore, and Yan Zhang)