### Rutgers Discrete Mathematics Seminar

Title: Improved Approximation for the Directed Spanner Problem

Speaker: **Arnab Bhattacharyya**, Princeton University

Date: Tuesday, September 13, 2011 2:00pm

Location: Hill Center, Room 425, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:
We present an O(sqrt(n) log n)-approximation algorithm for the
problem of finding the sparsest spanner of a given *directed* graph G
on n vertices. A spanner of a graph is a sparse subgraph that
approximately preserves distances in the original graph. More
precisely, given a graph G=(V,E) with nonnegative real edge lengths
and a stretch parameter k>= 1, a subgraph H = (V,E') is a k-spanner of
G if for every edge (s,t) in E, the graph H contains a path from s to
t of length at most k times the length of the shortest path from s to
t in G. The previous best approximation ratio was O~(n^{2/3}), due to
Dinitz and Krauthgamer (STOC '11). We also improve the approximation
ratio for the important special case of directed 3-spanners with unit
edge lengths from O~(sqrt{n}) to O(n^{1/3} log n). The best previously
known algorithms for this problem are due to Berman, Raskhodnikova and
Ruan (FSTTCS '10) and Dinitz and Krauthgamer. The approximation ratio
of our algorithm almost matches Dinitz and Krauthgamer's lower bound
for the integrality gap of a natural linear programming
relaxation. Our algorithm directly implies an O(n^{1/3} log
n)-approximation for the k-spanner problem on undirected graphs with
unit lengths. An easy O(sqrt{n})-approximation algorithm for this
problem has been the best known for decades.

Joint work with Piotr Berman, Konstantin Makarychev, Sofya Raskhodnikova and Grigory Yaroslavtsev.