• Calendar

April 5, Tuesday
12:00 – 13:00

A k-spanner of a given graph is a subgraph that preserves all distances within factor k. This notion is useful in several contexts, from distributed computing to property testing. From an algorithmic viewpoint, the goal is to find a k-spanner with as few edges as possible. In this talk I will examine two variants of graph spanners: directed spanners and fault-tolerant spanners. In the directed setting we design an O(n^{2/3})-approximation algorithm for the directed k-spanner problem that works for all k. This is the first approximation independent of k, as well as being the first to handle arbitrary edge lengths. In the fault-tolerant setting we give a new construction of fault-tolerant spanners of undirected graphs that is both simpler than previous work and improves the dependence on the number of faults from exponential to polynomial. For the special case of k=2, we also provide an O(log n)-approximation algorithm for the smallest fault-tolerant 2-spanner. This approximation ratio is, notably, independent of the number of faults. Our main tool in both the directed and fault-tolerant settings is a new flow-based linear programming relaxation.

Joint work with Robert Krauthgamer.