Title: Approximating Shortest Paths with Purely Additive Spanners
Speaker: Seth Pettie
Date: May 26, 2005 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
An additive k-spanner of a graph is a subgraph whose distance metric approximates that of the original graph to within an additive error of k. (Graphs are undirected and unweighted). It is known that every graph contains an additive 2-spanner with O(n^{3/2}) edges and that this bound is tight. Until the present work no other additive spanners were known and their existence was very much in doubt.
In this talk I'll discuss a new approach to computing spanners based on an economics inspired view of the problem. Our primary result is that every graph contains an additive 6-spanner with O(n^{4/3}) edges. The same method is used to prove several lesser results.