The Taub Faculty of Computer Science Events and Talks

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. By examining spanners through flow-based linear programming relaxations, we design an O(n^{2/3})-approximation algorithm for the directed k-spanner problem that works for all k. This is the first sublinear approximation for arbitrary edge-lengths. We also design a different rounding scheme with a better approximation ratio for the special case of k=3 and unit edge lengths. Our algorithms easily extend to the fault-tolerant setting, which has recently attracted attention but not from an approximation viewpoint. A virtue of all of our algorithms is that they are relatively simple.

Joint work with Robert Krauthgamer