CSAIL Event Calendar
[A&C Seminar] Highway Dimension: From Practice to Theory and Back
Speaker: Andrew V. Goldberg, Microsoft Research -- Silicon Valley
Date: Wednesday, February 20 2013
Time: 4:00PM to 5:00PM
Host: Piotr Indyk, MIT
Contact: Eric Price, firstname.lastname@example.orgRelevant URL: http://www.mit.edu/~ecprice/algcompsem/
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. The underlying algorithms are highly practical and intuitive, but until recently there was no theoretical explanation of their practical performance. We review some of these algorithms and give the first theoretical analysis for them on a non-trivial class of networks.