April 4, Wednesday 14:15, Room 303, Jacobs Building

Title: Approximation Algorithms for Graph Spanners

Lecturer: Michael Dinitz

Lecturer homepage : http://www.cs.cmu.edu/~mdinitz/

Affiliation : Weizmann Institute

Given a graph G, a k-spanner of G is a subgraph is which all distances are preserved up to a factor of k. In this talk I will discuss recent progress on approximation algorithms for various problems related to spanners. In particular, I will discuss new approximation algorithms for the directed k-spanner problem, as well as a new approximation algorithm for the lowest degree 2-spanner problem. These algorithms make extensive use of linear programming relaxations, including a new relaxation based on a combination of "local" LPs that have been lifted with the Sherali-Adams hierarchy. This is in contrast to the previous techniques that have been used to approximate spanners, which have been mostly combinatorial. Joint work with Eden Chlamtac and Robert Krauthgamer