CATS-Dec-4-2012
Title
Revisiting The Monge Property
Speaker
Dr. Golin is a Professor in the Department of Computer Science & Engineering at HKUST. He is also Associate Vice-President for Postgraduate Studies. After receiving his doctorate from Princeton University in 1990, Dr. Golin worked as a researcher in the Projet Algorithmes of the Institut National de Recherche en Informatique et en Automatique (INRIA) in Rocquencourt, France. He has also been a visiting researcher at the Max-Planck-Institut fur Informatik in Saarbrucken, Germany, INRIA-Sophia in France, AT&T Labs-Research, and DIMACS. His research interests include the design and application of algorithms, computational geometry, information theory, and combinatorics.
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).
This is joint work with Amotz Bar-Noy, Yi Feng, Larry Larmore and Yan Zhang