CSAIL Event Calendar: Previous Series

Low-distortion Graph Spanners

Speaker: Seth Pettie , Max Planck Institute
Date: April 13 2006
Time: 4:00PM to 5:15AM
Location: 32-G575
Host: Mihai Patrascu, MIT CSAIL

Contact: Joanne Hanley, 617.253.6054, joanne@csail.mit.edu
Relevant URL: http://theory.csail.mit.edu/~madhu/algcomp/pettie-abs.html

A spanner H of an undirected, unweighted graph G is a subgraph such that the distance between two points w.r.t. H is not too far from their distance in G, where "not too far" is captured by a distortion function f. Specifically, H is an f-spanner if dist_H(u,v) is at most f(dist_G(u,v)). Nearly all work on spanners and related structures considered only multiplicative distortion, and, in general, provided an undesirable tradeoff between the size of H and the coefficient of distortion.

The "holy grail" question in this area is whether there exist arbitrarily sparse spanners whose distortion is additive and constant. It was known that any graph has an additive 2-spanner with O(n^{3/2}) edges. In this talk I'll present a completely new method for constructing spanners based on an economics-inspired view of the problem. The main result is an additive 6-spanner with O(n^{4/3}) edges. In addition, the technique leads to a spectrum of arbitrarily sparse spanners whose distortion is additive and sublinear in the distance being approximated.

See other events that are part of Algorithms and Complexity Spring 2006

See other events happening in April 2006