论文标题
几何施泰纳森林的流算法
Streaming Algorithms for Geometric Steiner Forest
论文作者
论文摘要
我们考虑了史坦纳树问题的重要概括，即\ emph {Steiner森林问题}，在欧几里得飞机上：输入是一个多动物$ x \ subseteq \ subseteq \ subseteq \ mathbb {r}^2 $，分为$ k $ k $ k $ cololy类$ c_1，c_1，c_1，c_2，c_2，\ ldots，\ ldots，c_k \ sepSeteeq x $。目标是找到一个最低成本的欧几里得图$ g $，以便每个颜色类$ c_i $都以$ g $连接。我们在流媒体环境中研究了施泰纳森林问题，该流包括插入和删除$ x $的点。 x $中的每个输入点$ x \ in color $ \ textsf {color}（x）\在[k] $中，并且与往常一样，对于动态几何流，输入点仅限于离散网格$ \ {0，\ ldots，x \ ldots，δ\}^2 $。 We design a single-pass streaming algorithm that uses $\mathrm{poly}(k \cdot \logΔ)$ space and time, and estimates the cost of an optimal Steiner forest solution within ratio arbitrarily close to the famous Euclidean Steiner ratio $α_2$ (currently $1.1547 \le α_2 \le 1.214$).此近似保证与流式施流式施流式施材的最新限制相匹配，即当$ k = 1 $时，这是一个主要的开放式问题，即使对于此特殊情况，将比率提高到$ 1 +ε$。我们的方法取决于流媒体技术的新型组合，例如采样和线性素描，以及用于几何优化问题的经典Arora风格的动态编程框架，这些框架通常需要大记忆，迄今为止尚未在流设置中应用。 我们为Steiner Forest问题提供了流媒体算法的补充，简单的论点表明任何有限的近似都需要$ω（k）$的空间。
We consider an important generalization of the Steiner tree problem, the \emph{Steiner forest problem}, in the Euclidean plane: the input is a multiset $X \subseteq \mathbb{R}^2$, partitioned into $k$ color classes $C_1, C_2, \ldots, C_k \subseteq X$. The goal is to find a minimum-cost Euclidean graph $G$ such that every color class $C_i$ is connected in $G$. We study this Steiner forest problem in the streaming setting, where the stream consists of insertions and deletions of points to $X$. Each input point $x\in X$ arrives with its color $\textsf{color}(x) \in [k]$, and as usual for dynamic geometric streams, the input points are restricted to the discrete grid $\{0, \ldots, Δ\}^2$. We design a single-pass streaming algorithm that uses $\mathrm{poly}(k \cdot \logΔ)$ space and time, and estimates the cost of an optimal Steiner forest solution within ratio arbitrarily close to the famous Euclidean Steiner ratio $α_2$ (currently $1.1547 \le α_2 \le 1.214$). This approximation guarantee matches the state-of-the-art bound for streaming Steiner tree, i.e., when $k=1$, and it is a major open question to improve the ratio to $1 + ε$ even for this special case. Our approach relies on a novel combination of streaming techniques, like sampling and linear sketching, with the classical Arora-style dynamic-programming framework for geometric optimization problems, which usually requires large memory and has so far not been applied in the streaming setting. We complement our streaming algorithm for the Steiner forest problem with simple arguments showing that any finite approximation requires $Ω(k)$ bits of space.
