Introduction to additive spanners

Abstract:

A graph spanner is a sparse subgraph of a given graph that approximately preserves the pairwise distances of the original graph.

Graph spanners were extensively studied since their introduction in the late 80's, and they are considered a fundamental structure as they are a key ingredient in many applications in distributed computation.

Much of the previous work focuses on multiplicative spanners, that is when the approximation guarantee is measured by the worst case ratio between distances in the spanner and distances in the original graph.

A much stronger guarantee is to obtain additive approximation, i.e., finding spanners whose distances are at most the distances in the original graph plus some additive term.

In this talk an introduction to spanners will be given and in particular additive spanners.