Hop-Constrained Metric Embeddings and their Applications
Hop-Constrained Metric Embeddings and their Applications
复制标题
跳数约束的度量嵌入及其应用
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Arnold Filtser
中科院分区：
文献类型：
--
作者：
Arnold Filtser
在网络设计问题中，例如紧凑路由，目标是使用（近似的）最短路径在节点之间路由数据包。这些路由的一个理想特性是跳数少，这使它们更可靠，并降低传输成本。随着随机树嵌入在算法设计中取得巨大成功，豪普勒（Haeupler）、赫什科维茨（Hershkowitz）和祖齐奇（Zuzic）（STOC'21）研究了到树的跳数受限的拉姆齐型度量嵌入。具体来说，嵌入$f: G(V, E)\rightarrow T$具有拉姆齐跳数失真（$t, M,\beta, h$）（这里$t, \beta, h\geq 1$且$M\subseteq V$），如果对于任意$u\in M$，$v\in V$，有$d_{G}^{(\beta\cdot h)}(u, v)\leq d_{T}(u, v)\leq t\cdot d_{G}^{(h)}(u, v)$。$t$被称为失真，$\beta$被称为跳数拉伸，$d_{G}^{(h)}(u, v)$表示最多有$h$跳的$u - v$路径的最小权重。豪普勒等人构建了嵌入，其中$M$包含$1 - \epsilon$比例的顶点，且$\beta = t = O(\frac{\log^{2}n}{\epsilon})$。他们利用他们的嵌入为跳数受限的网络设计问题获得了多个双准则近似算法。在本文中，我们首先改进拉姆齐型嵌入以获得参数$t = \beta = \frac{\tilde{O}(\log n)}{\epsilon}$，并将其推广到任意失真参数$t$（以减小$M$的大小为代价）。这种嵌入立即意味着对豪普勒等人的所有近似算法有多项式改进。此外，我们构建跳数受限的族嵌入（其中每个顶点有多个副本），并利用它们为组斯坦纳树问题构建双准则近似算法，与无约束版本的现有技术水平相匹配。最后，我们利用我们的嵌入结果构建跳数受限的距离预言机、距离标记，最显著的是，第一个具有可证明保证的跳数受限紧凑路由方案。我们所有的度量数据结构几乎与无约束版本的现有技术水平参数相匹配。
In network design problems, such as compact routing, the goal is to route packets between nodes using the (approximated) shortest paths. A desirable property of these routes is a small number of hops, which makes them more reliable, and reduces the transmission costs. Following the overwhelming success of stochastic tree embeddings for algorithmic design, Haeupler, Hershkowitz, and Zuzic (STOC'21) studied hop-constrained Ramsey-type metric embeddings into trees. Specifically, embedding $f: G(V, E)\rightarrow T$ has Ramsey hop-distortion ($t, M,\beta, h$), (here $t, \beta, h\geq 1$ and $M\subseteq V)$ if $\forall u\in M, v\in V,\ d_{G}^{(\beta\cdot h)}(u, v)\leq d_{T}(u, v)\leq t\cdot d_{G}^{(h)}(u, v). t$ is called the distortion, $\beta$ is called the hop-stretch, and $d_{G}^{(h)}(u, v)$ denotes the minimum weight of a $u-v$ path with at most $h$ hops. Haeupler et al. constructed embedding where $M$ contains $1-\epsilon$ fraction of the vertices and $\beta=t=O(\frac{\log^{2}n}{\epsilon})$. They used their embedding to obtain multiple bicriteria approximation algorithms for hop-constrained network design problems. In this paper, we first improve the Ramsey-type embedding to obtain parameters $t=\beta=\frac{\tilde{O}(\log n)}{\epsilon}$, and generalize it to arbitrary distortion parameter $t$ (in the cost of reducing the size of $M$). This embedding immediately implies polynomial improvements for all the approximation algorithms from Haeupler et al.. Further, we construct hop-constrained clan embeddings (where each vertex has multiple copies), and use them to construct bicriteria approximation algorithms for the group Steiner tree problem, matching the state of the art of the non constrained version. Finally, we use our embedding results to construct hop constrained distance oracles, distance labeling, and most prominently, the first hop constrained compact routing scheme with provable guarantees. All our metric data structures almost match the state of the art parameters of the non-constrained versions.
跳数约束的不经意路由
DOI：
10.1145/3406325.3451098
发表时间：
2021
期刊：
Symposium on Theory of Computing (STOC
影响因子：
--
作者：
Ghaffari, Mohsen;Haeupler, Bernhard;Zuzic, Goran
通讯作者：
Zuzic, Goran
通过低跳模拟器并行近似无向最短路径
DOI：
10.1145/3357713.3384321
发表时间：
2020
期刊：
Symposium on Theory of Computing (STOC
影响因子：
--
作者：
Andoni, Alexandr;Stein, Clifford;Zhong, Peilin
通讯作者：
Zhong, Peilin
用于跳数受限网络设计的树嵌入
DOI：
10.1145/3406325.3451053
发表时间：
2021
期刊：
Symposium on Theory of Computing (STOC
影响因子：
--
作者：
Haeupler, Bernhard;Hershkowitz, D. Ellis;Zuzic, Goran
通讯作者：
Zuzic, Goran