# Theory Seminar: From Hierarchical Partitions to Hierarchical Covers: Optimal Fault-Tolerant Spanners for Doubling Metrics

Speaker:
Shay Solomon (Weizmann Institute of Science)
Date:
Wednesday, 22.5.2013, 12:30
Place:
Taub 201
A {\em $(1+\eps)$-spanner} for a doubling metric $(X,\delta)$ is a subgraph $H$ of the complete graph corresponding to $(X,\delta)$, which preserves all pairwise distances to within a factor of $1+\eps$. A natural requirement from a spanner is to be robust against node failures, so that even when some of the nodes in the network fail, the remaining part would still provide a $(1+\eps)$-spanner. The spanner $H$ is called a {\em $k$-fault-tolerant $(1+\eps)$-spanner}, for any $0 \le k \le n-2$, if for any subset $F \subseteq X$ with $|F| \le k$, the graph $H \setminus F$ (obtained by removing from $H$ the vertices of $F$ and their incident edges) is a $(1+\eps)$-spanner for $X \setminus F$.
In this talk I will show how to obtain an optimal construction of fault-tolerant spanners for doubling metrics. Specifically, for any $n$-point doubling metric, any $\eps > 0$, and any integer $0 \le k \le n-2$, our construction provides a $k$-fault-tolerant $(1+\eps)$-spanner with optimal degree $O(k)$ within optimal time $O(n \log n + k n)$. We then strengthen this result to provide near-optimal (up to a factor of $\log k$) guarantees on the diameter and weight of our spanners.