Shortest Paths in Practice – University of Copenhagen

Shortest Paths in Practice

Talk by Renato Werneck, Friday, September 12, 14:00-15:00

HCØ AUD 9 (1.sal på svalegangen)

Abstract

Computing shortest paths on massive networks is a basic building block for several applications, such as finding driving directions in road networks. For inputs with millions of vertices, even linear-time search-based algorithms can be too slow for practical use. Modern techniques thus use a preprocessing stage to compute some auxiliary data, which is then used to answer (exact) queries interactively. Different algorithms enable various trade-offs between preprocessing effort, query times, space usage, simplicity, and extensibility. I will survey the state of the art in this area, with emphasis on algorithms for road networks. The talk should be accessible to a wide audience and will include a live demo of the algorithm currently in use by Microsoft's Bing Maps.

About Renato Werneck

Renato Werneck is a Senior Researcher at Microsoft Research Silicon Valley. He obtained his PhD degree in Computer Science from Princeton University in 2006, after receiving a B.Eng. and an M.Sc. in his native Brazil. His research interests include algorithm engineering, data structures, graph algorithms, and combinatorial optimization. He serves on the steering committee of ALENEX, on the editorial board of Mathematical Programming Computation (MPC), and as organizer of the upcoming DIMACS Implementation Challenge on Steiner Tree Problems.