Paper Info
Title
Locality-Sensitive Orderings and Applications to Reliable Spanners
Abstract
Chan, Har-Peled, and Jones [2020] recently developed locality-sensitive ordering (LSO), a new tool that allows one to reduce problems in the Euclidean space R-d to the 1-dimensional line. They used LSO's to solve a host of problems. Later, Buchin, Har-Peled, and Olah [2019,2020] used the LSO of Chan et al. to construct very sparse reliable spanners for the Euclidean space. A highly desirable feature of a reliable spanner is its ability to withstand a massive failure: the network remains functioning even if 90% of the nodes fail. In a follow-up work, Har-Peled, Mendel, and Olah [2021] constructed reliable spanners for general and topologically structured metrics. Their construction used a different approach, and is based on sparse covers. In this paper, we develop the theory of LSO's in non-Euclidean metrics by introducing new types of LSO's suitable for general and topologically structured metrics. We then construct such LSO's, as well as constructing considerably improved LSO's for doubling metrics. Afterwards, we use our new LSO's to construct reliable spanners with improved stretch and sparsity parameters. Most prominently, we construct (O) over tilde (n)-size reliable spanners for trees and planar graphs with the optimal stretch of 2. Along the way to the construction of LSO's and reliable spanners, we introduce and construct ultrametric covers, and construct 2-hop reliable spanners for the line.
Year
DOI
Venue
2022
10.1145/3519935.3520042
PROCEEDINGS OF THE 54TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '22)
Keywords
DocType
ISSN
Locality-Sensitive Orderings, Reliable Spanners, Doubling Metric, Ultrametric cover, 2-hop spanners, Minor Free graphs
Conference
0737-8017
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Arnold Filtser100.68
Hung Le200.34