אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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.

Our result settles several fundamental open questions in this area, culminating a long line of research that started with the STOC'95 paper of Arya et al. and the STOC'98 paper of Levcopoulos et al. On the way to this result we develop a new technique for constructing spanners in doubling metrics. In particular, our spanner construction is based on a novel {\em hierarchical cover} of the metric, whereas most previous constructions of spanners for doubling and Euclidean metrics (such as the net-tree spanner) are based on {\em hierarchical partitions} of the metric.

The talk will be self-contained. During the talk I will present some open problems in this area.