[talks] Colloquium Speaker-Wednesday, October 14, 2009

[Michele J. Brown]

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)
4:30 PM

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.