[Colloquium] REMINDER: Aaron Bernstein Talk Today
Katie Casey
caseyk at cs.uchicago.edu
Tue Mar 30 08:49:33 CDT 2010
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.
More information about the Colloquium
mailing list