Skip to content (access key 's')
Logo of Technion
Logo of CS Department


Theory Seminar: Directed Spanners via Flow-Based Linear Programs
event speaker icon
Michael Dinitz (Weizmann Institute)
event date icon
Wednesday, 1.6.2011, 12:30
event location icon
Room 337-8 Taub Bld.
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
[Back to the index of events]