Bureaucrats, editor, Administrators
373
edits
Changes
From Theory
no edit summary
== 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
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
