[Colloquium] Guest Speakers @ TTI-C Today (3/7/06)

[Katherine Cumming]

**********TTI-C Guest Speaker Today***********
                      March 7, 2006
        Presented by:  Toyota Technological Institute at Chicago
 
Speaker:  Seth Pettie, Max Plank Institute
Speaker's home page: http://www.mpi-sb.mpg.de/~pettie/
 
Date: Tuesday, March 7, 2006 
Location: TTI-C Conference Room
Time:  10:00 am
 
Title: Finding the Shortest Path
Abstract:
What's the shortest route from point A to point B? This is a fundamental
algorithmic question with deep connections to other optimization problems
and numerous practical applications. The most well known applications are
services like Google Maps, OnStar, and MapQuest, which will quickly answer
shortest path queries on the U.S. road network. Although shortest path
algorithms are relatively fast in practice, the inherent time complexity of
computing shortest paths is unresolved. In fact, on general graphs this
problem has seen surprisingly little progress since the invention of the
"textbook" algorithms of Dijkstra, Bellman-Ford, and Floyd-Warshall in the
late 1950s.

In the first part of this talk, I'll present an asymptotically faster
all-pairs shortest path algorithm for general graphs. This is the first such
algorithm to improve the running time of Dijkstra's algorithm.

In many scenarios, finding shortest paths is only the beginning. The more
challenging problem is to encode shortest path information in a succinct and
usable way. (For instance, in the form of routing tables distributed across
the nodes of a network.) In the second part of the talk, I'll discuss my
work on low-distortion spanners, which are objects that efficiently encode
approximately shortest paths. 
 
----------------------------------------------------------------------------
------
If you have questions, or would like to meet the speaker, please contact
Katherine at 773-834-1994 or kcumming at tti-c.org.   
For information on future TTI-C talks and events, please go to the TTI-C
Events page:  http://www.tti-c.org/events.html.  TTI-C (1427 East 60th
Street, Chicago, IL  60637)
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20060307/7bd14bef/attachment.htm