Johns Hopkins Algorithms and Complexity
https://www.cs.jhu.edu/~mdinitz/theory
America/New_York
America/New_York
America/New_York
20221106T020000
-0400
-0500
EST
20230312T020000
-0500
-0400
EDT
ai1ec-349@www.cs.jhu.edu/~mdinitz/theory
20221126T113618Z
Speaker: Hung Le
Affiliation: University of Massachusetts, Amherst
Title: Reliable Spanners: Locality-Sensitive Orderings Strike Back
Abstract:
A highly desirable property of networks is robustness to failures.
Consider a metric space $(X,d_X)$, a graph $H$ over $X$ is a $\vartheta$-reliable $t$-spanner if, for every set of failed vertices $B\subset X$, there is a superset $B^ \supseteq B$ such that the induced subgraph $H[X\setminus B]$ preserves all the distances between points in $X\setminus B^ $ up to a stretch factor $t$, while the expected size of $B^ $ is as most $(1 \vartheta)|B|$. Such a spanner could withstand a catastrophe: failure of even $90\%$ of the network.
Buchin, Har-Peled, and Olah showed how to construct a sparse reliable spanner for Euclidean space from Euclidean locality-sensitive orderings, an object introduced by Chan, Har-Peled, and Jones. In this talk, we extend their approach to non-Euclidean metric spaces by generalizing the ordering of Chan, Har-Peled, and Jones to doubling metrics and introducing new types of locality-sensitive orderings for other metric spaces. We also show how to construct reliable spanners from the newly introduced locality-sensitive orderings via reliable 2-hop spanners for paths. The highlight of our results is that the number of edges in our spanner has no dependency on the spread.
20210303T120000
20210303T130000
https://wse.zoom.us/j/91450299380
0
[Theory Seminar] Hung Le
free