Speaker: Christian Sommer MIT
Time: 2012-03-14 10:40-2012-03-14 11:40
Venue: FIT 1-222
Abstract:
We discuss the problem of efficiently computing a shortest path between two nodes of a network --- a problem with numerous applications. The shortest-path query problem in particular occurs in transportation (route planning and navigation or also logistics and traffic simulations), in packet routing, in social networks, and in many other scenarios. Furthermore, shortest-path problems occur as subproblems in various optimization problems.
Strategies for computing answers to shortest-path queries may involve the use of pre-computed data structures (also called distance oracles) in order to improve the query time. Designing a shortest-path-query processing method raises questions such as: How can these data structures be computed efficiently? What amount of storage is necessary? How much improvement of the query time is possible? How good is the approximation quality (also termed stretch) of the query result? And, in particular, what are the tradeoffs between pre-computation time, storage, query time, and approximation quality?
The talk provides answers to these questions for static networks. In particular, we consider the tradeoff between storage and query time, both from a theoretical and from an experimental perspective. We focus on two application scenarios: First, we discuss shortest-path query methods for planar graphs, motivated by route planning in road networks. Second, we discuss distance oracles and shortest-path query methods for complex networks, motivated by small-world phenomena in social networks and Internet routing. We also outline which methods and techniques can or cannot be extended to more general networks.
Joint work with Takuya Akiba, Wei Chen, Ken-ichi Kawarabayashi, Philip Klein, Shay Mozes, Shang-Hua Teng, Mikkel Thorup, Elad Verbin, Yajun Wang, Wei Yu, and others
Short Bio:
Christian Sommer is a researcher in Computer Science, currently as a Postdoctoral Fellow at the Massachusetts Institute of Technology. He got his MSc from ETH Zurich in 2006 and his PhD from the University of Tokyo in 2010, where he also received the Dean's award for the best PhD thesis in the Computer Science Department. His research interests are algorithms, data structures, and graphs.
