SPEAKER: Michael Dinitz

TIME: Wednesday 12-1pm, September 27, 2006

PLACE: NSH 1507

TITLE: Spanners with Slack

ABSTRACT:
Given a metric (V,d), a spanner is a sparse graph whose shortest-path metric
approximates the distance d to within a small multiplicative distortion;
spanners have been widely studied in the literature for over two decades, and
a variety of tight results are known. For instance, it is known that any
metric has a spanner with O(n) edges that approximates distances to within an
O(log n) distortion.

In this talk we study the problem of spanners with slack: e.g., can we find
sparse spanners where we are allowed to incur an arbitrarily large distortion
on a constant fraction of the distances, but are then required to incur only
a constant (independent of n) distortion on the remaining distances? We
answer this question in the affirmative, thus complementing similar recent
results on embeddings with slack into L_p spaces. For instance, we show that
if we ignore an epsilon fraction of the distances, we can get spanners with 
O(n) edges and O(log(1/epsilon)) distortion for the remaining distances.

Among other results in this talk, we show how to obtain sparse and low-weight
spanners with slack from existing constructions of conventional spanners, and
these techniques allow us to also obtain the best known results for distance
oracles and distance labelings with slack. Finally, we also review notions of
average distortion (without slack) previously studied in the literature, and
show that our slack spanner constructions give us constant average distortion
spanners.

This is joint work with Hubert Chan and Anupam Gupta