[Colloquium] Talk by Aaron Bernstein, MIT on March 30, 2010

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, March 30, 2010
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------------------

Speaker:	Aaron Bernstein

From:		MIT

Title: Improved Approximation Algorithms for Dynamic Shortest Paths: Breaking Through the O(n) Update Time Barrier

Abstract: In the /dynamic shortest paths problem/, the goal is to maintain shortest path information in a graph whose edges are being inserted or deleted over time. More formally, we must process an online sequence of update and query operations, where an update operation inserts or deletes an edge from the underlying graph, while a query operation asks for the shortest distance/path between two vertices. We focus on the /decremental/ version, in which edges are only deleted, never inserted. There exist many different algorithms for this problem, both exact and approximate, but even with approximation all of these algorithm stop at a natural barrier of an O(n) amortized update time. We present the first two algorithms to break through this barrier. Both are for unweighted, undirected graphs. For singer source shortest paths, we present a (1 + epsilon) approximation algorithm with amortized update time around O(n^2/m) (a bit worse). For all pairs shortest paths, we achieve a trade-off between update time and approximation error. For example, our framework achieves a (3 + epsilon)-approximation with an amortized update time of about O(n^{2.5}/m). The key to our algorithms is a general technique for accelerating decremental algorithms; we achieve our results by applying the technique to two particular decremental algorithms, but it could be applied to others as they come up.