论文标题
流欧几里得最大切割：尺寸与数据减少
Streaming Euclidean Max-Cut: Dimension vs Data Reduction
论文作者
论文摘要
最大切割是一个基本问题，已在各种环境中进行了广泛的研究。我们为欧几里得最大切割设计了一种算法，其中输入是$ \ m athbb {r}^d $中的一组点，在动态几何流中，其中输入$ x \ subseteq [δ]^d $作为点插入和删除的顺序表示。以前，Frahling和Sohler [Stoc 2005]设计了低维度的$（1+ε）$ - 近似算法，即，它使用Space $ \ exp（d）$。 为了解决越来越感兴趣的高维度中的问题，必须改善对尺寸$ d $的依赖，理想情况下，对空间复杂性$ \ mathrm {poly}（ε^{ - 1} d \logΔ）$。 Lammersen，Sidiropoulos和Sohler [Wads 2009]证明，Euclidean Max-Cut在目标尺寸$ d'= \ Mathrm {Poly}（ε^{ - 1}）$中降低了尺寸。将其与使用Space $ \ exp（d'）$的上述算法相结合，他们获得了一种算法，其整体空间复杂性确实在$ d $中是多项式，但不幸的是，指数为$ε^{ - 1} $。 我们根据重要性采样设计了一种\ emph {数据降低}的替代方法，并实现了空间绑定的$ \ mathrm {poly}（ε^{ - 1} d \logδ）$，该$比dimension-reduction方法呈指数优于（以$ε$）更好。为了在流模型中实现此方案，我们使用随机移动的Quadtree来构造树嵌入。虽然这是一种众所周知的方法，但我们算法的关键特征是嵌入的失真$ o（d \logδ）$仅影响空间复杂性，并且近似值仍然保持$ 1+ε$。
Max-Cut is a fundamental problem that has been studied extensively in various settings. We design an algorithm for Euclidean Max-Cut, where the input is a set of points in $\mathbb{R}^d$, in the model of dynamic geometric streams, where the input $X\subseteq [Δ]^d$ is presented as a sequence of point insertions and deletions. Previously, Frahling and Sohler [STOC 2005] designed a $(1+ε)$-approximation algorithm for the low-dimensional regime, i.e., it uses space $\exp(d)$. To tackle this problem in the high-dimensional regime, which is of growing interest, one must improve the dependence on the dimension $d$, ideally to space complexity $\mathrm{poly}(ε^{-1} d \logΔ)$. Lammersen, Sidiropoulos, and Sohler [WADS 2009] proved that Euclidean Max-Cut admits dimension reduction with target dimension $d' = \mathrm{poly}(ε^{-1})$. Combining this with the aforementioned algorithm that uses space $\exp(d')$, they obtain an algorithm whose overall space complexity is indeed polynomial in $d$, but unfortunately exponential in $ε^{-1}$. We devise an alternative approach of \emph{data reduction}, based on importance sampling, and achieve space bound $\mathrm{poly}(ε^{-1} d \logΔ)$, which is exponentially better (in $ε$) than the dimension-reduction approach. To implement this scheme in the streaming model, we employ a randomly-shifted quadtree to construct a tree embedding. While this is a well-known method, a key feature of our algorithm is that the embedding's distortion $O(d\logΔ)$ affects only the space complexity, and the approximation ratio remains $1+ε$.
