Theory Seminar: Directed Spanners via Flow-Based Linear Programs

דובר:
מיכאל דיניץ (מכון ויצמן למדע)
תאריך:
יום רביעי, 1.6.2011, 12:30
מקום:
חדר 337, בניין טאוב למדעי המחשב

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

בחזרה לאינדקס האירועים