Locality-Sensitive Orderings and Applications to Reliable Spanners
Locality-Sensitive Orderings and Applications to Reliable Spanners
复制标题
区域敏感的排序和可靠 Spanner 的应用
DOI：
10.1145/3519935.3520042
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Le, Hung
中科院分区：
文献类型：
--
作者：
Filtser, Arnold;Le, Hung
Chan，Har-Peled和Jones [2020]最近开发了局部敏感排序（LSO），这是一种新工具，可以将欧几里得空间中的问题简化为一维线。他们用LSO解决了很多问题。后来，Buchin，Har-Peled和Oláh [2019，2020]使用Chanet al.to的LSO为欧几里得空间构造了非常稀疏可靠的生成器。可靠的网络的一个非常理想的特性是它能够承受大规模故障：即使90%的节点发生故障，网络仍然可以正常运行。在后续的工作中，Har-Peled，Mendel和Oláh [2021]为一般和拓扑结构的度量构建了可靠的spectrum。他们的建设使用了不同的方法，是基于稀疏covers.In本文中，我们开发的理论LSO的非欧度量引入新类型的LSO的一般和拓扑结构的度量合适的。然后，我们构建这样的LSO的，以及构建大大改进的LSO的加倍度量。之后，我们使用我们的新的LSO的构造可靠的spectum与改进的拉伸和稀疏参数。最突出的是，我们构造了树和平面图的最佳拉伸为2的n（n）-大小的可靠空间。沿着构造LSO和可靠空间的道路，我们引入并构造了超度量覆盖，并构造了线路的2跳可靠空间。
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 ℝdto the 1-dimensional line. They used LSO’s to solve a host of problems. Later, Buchin, Har-Peled, and Oláh [2019,2020] used the LSO of Chanet al.to construct very sparsereliable spannersfor 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 Oláh [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 Õ(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.