论文标题
混合网络模型中的距离计算通过Oracle模拟
Distance Computations in the Hybrid Network Model via Oracle Simulations
论文作者
论文摘要
在[Augustine等人，SODA '20]中引入了混合网络模型，用于为网络奠定理论基础，该网络结合了两种可能的通信方式：一种模式允许与相邻节点进行高带宽通信，而另一个模式可以一次在几个长期的长距离连接中进行低频带的通信。从根本上讲，这从混合数据中心和基于班级的软件定义网络等网络中进行了摘要。 我们的技术贡献是\ emph {密度 - 意识}方法，它使我们能够模拟一组\ emph {oracles}，以在混合网络上使用覆盖骨架图。 作为我们的Oracle仿真的应用，我们提供了其他机械，我们为基本与距离相关的任务提供了快速算法。我们的核心贡献之一是用于计算\ emph {eckect}加权的混合模型中的算法，从$ \ tilde o（n^{1/3}）$源从$ \ tilde o（n^{1/3}）$来源完成，该路径以$ \ tilde o（n^{1/3}）$ rounds $ rounds $ rounds w.h.p.在[Kuhn和Schneider，PODC '20]的算法上，这在运行时和来源的数量中都改善了，该算法从$ \ tilde o中的单个源计算最短路径（n^{2/5}）$ rounds $ rounds w.h.p。 另外，我们还显示了加权直径的2个附属物和$（1+ε）$ - 未加权直径的近似值，均以$ \ tilde o（n^{1/3}）$（n^{1/3}）$ rounds w.h.p. $（2-ε）$ - 加权直径和确切的未加权直径的近似。我们还从多个来源提供快速距离\ emph {近似值}，以及偏心率的快速近似值。
The Hybrid network model was introduced in [Augustine et al., SODA '20] for laying down a theoretical foundation for networks which combine two possible modes of communication: One mode allows high-bandwidth communication with neighboring nodes, and the other allows low-bandwidth communication over few long-range connections at a time. This fundamentally abstracts networks such as hybrid data centers, and class-based software-defined networks. Our technical contribution is a \emph{density-aware} approach that allows us to simulate a set of \emph{oracles} for an overlay skeleton graph over a Hybrid network. As applications of our oracle simulations, with additional machinery that we provide, we derive fast algorithms for fundamental distance-related tasks. One of our core contributions is an algorithm in the Hybrid model for computing \emph{exact} weighted shortest paths from $\tilde O(n^{1/3})$ sources which completes in $\tilde O(n^{1/3})$ rounds w.h.p. This improves, in both the runtime and the number of sources, upon the algorithm of [Kuhn and Schneider, PODC '20], which computes shortest paths from a single source in $\tilde O(n^{2/5})$ rounds w.h.p. We additionally show a 2-approximation for weighted diameter and a $(1+ε)$-approximation for unweighted diameter, both in $\tilde O(n^{1/3})$ rounds w.h.p., which is comparable to the $\tilde Ω(n^{1/3})$ lower bound of [Kuhn and Schneider, PODC '20] for a $(2-ε)$-approximation for weighted diameter and an exact unweighted diameter. We also provide fast distance \emph{approximations} from multiple sources and fast approximations for eccentricities.
