[talks] Colloquium Speaker-Wednesday, October 14, 2009
Michele J. Brown
mjbrown at CS.Princeton.EDU
Fri Oct 9 10:58:08 EDT 2009
Title: Highway Dimension and Provably Efficient Shortest Path Algorithms
Andrew Goldberg, Microsoft Research - Silicon Valley
Host: Robert Tarjan
Wednesday, October 14, 2009
Computer Science 105 (Small Auditorium)
Computing driving directions has motivated many shortest path heuristics
that answer queries on continental scale networks, with tens of millions
of intersections, in real time, and with very low storage overhead.
We give the first theoretical analysis of several underlying algorithms
on a non-trivial class of networks. To do this, we introduce the notion
of highway dimension. Our analysis works for networks with low highway
dimension and gives a unified explanation of good performance for
several seemingly different algorithms.
Joint work with Ittai Abraham, Amos Fiat, and Renato Werneck.
More information about the talks