Algorithms and Complexity Seminar
Thursday, March 16, 2006, 4-5:15pm in 32-G575.
Low-distortion Graph Spanners
Seth Pettie (Max Planck Institute)
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.
Host: Mihai Patrascu