Time: 1:00pm Tuesday 15 October
Location: SIT 459
Speaker: Mordecai Golin, HKUST
Title: Revisiting the Monge property
We revisit the generic “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).
This is joint work with Amotz Bar-Noy, Yi Feng, Larry Larmore and Yan Zhang.