论文标题
将欧几里得MST流式传输到一个恒定因素
Streaming Euclidean MST to a Constant Factor
论文作者
论文摘要
我们研究了计算$ n $ - 点集$ x \ subset \ mathbb {r}^d $的基本几何学问题的流算法。在流模型中，可以任意添加和删除$ x $中的点，目标是在小空间中保持近似值。在低维度中，$（1+ε）$ $近似在均匀空间[Frahling，Indyk，Sohler，SocG '05]。但是，对于高维空间，由于[Chen，Jayaram，Levi，Waingarten，Stoc '22]，最著名的近似值是$ \ tilde {o}（\ log n）$ '08]。在本文中，我们打破了对数屏障，并将第一个恒定因子均方根空间近似与欧几里得MST近似。对于任何$ε\ geq 1 $，我们的算法就可以在$ n^{o（ε）} $ space中获得$ \ tilde {o}（ε^{ - 2}）$近似。 我们通过证明任何单个通过算法的获得$ 1.10 $ - APPRXIMATION必须使用$ω（\ sqrt {n}）$ space，证明$（1+ε）$近似值在高维度中不可能，并且我们的algorithm近似不可能。尽管如此，我们证明了$（1+ε）$近似值在sublinear空间中可以使用$ o（1/ε）$通过流。更一般而言，对于任何$α\ geq 2 $，我们给出了$α$ - 通道流算法，该算法可实现$（1+ o（\ frac {\ loglogα+α+ 1} {αε}）$ n^{o（ε）} d^{o（1）$（1）} $ Space中的$ n^{o（αε}））$近似。我们的流算法是线性草图，因此扩展到大规模并行计算模型（MPC）。因此，我们的结果意味着在MPC模型中，在恒定数量的回合中，第一个$（1+ε）$ - 与Euclidean MST近似。
We study streaming algorithms for the fundamental geometric problem of computing the cost of the Euclidean Minimum Spanning Tree (MST) on an $n$-point set $X \subset \mathbb{R}^d$. In the streaming model, the points in $X$ can be added and removed arbitrarily, and the goal is to maintain an approximation in small space. In low dimensions, $(1+ε)$ approximations are possible in sublinear space [Frahling, Indyk, Sohler, SoCG '05]. However, for high dimensional spaces the best known approximation for this problem was $\tilde{O}(\log n)$, due to [Chen, Jayaram, Levi, Waingarten, STOC '22], improving on the prior $O(\log^2 n)$ bound due to [Indyk, STOC '04] and [Andoni, Indyk, Krauthgamer, SODA '08]. In this paper, we break the logarithmic barrier, and give the first constant factor sublinear space approximation to Euclidean MST. For any $ε\geq 1$, our algorithm achieves an $\tilde{O}(ε^{-2})$ approximation in $n^{O(ε)}$ space. We complement this by proving that any single pass algorithm which obtains a better than $1.10$-approximation must use $Ω(\sqrt{n})$ space, demonstrating that $(1+ε)$ approximations are not possible in high-dimensions, and that our algorithm is tight up to a constant. Nevertheless, we demonstrate that $(1+ε)$ approximations are possible in sublinear space with $O(1/ε)$ passes over the stream. More generally, for any $α\geq 2$, we give a $α$-pass streaming algorithm which achieves a $(1+O(\frac{\log α+ 1}{ αε}))$ approximation in $n^{O(ε)} d^{O(1)}$ space. Our streaming algorithms are linear sketches, and therefore extend to the massively-parallel computation model (MPC). Thus, our results imply the first $(1+ε)$-approximation to Euclidean MST in a constant number of rounds in the MPC model.
