Max-Cut is a fundamental problem that has been studied extensively in various settings. We study Euclidean Max-Cut, where the input is a set of points in Rd, in the model of dynamic geometric streams, that is, the input is X⊆[Δ]d presented as a sequence of point insertions and deletions. Previous results by Frahling and Sohler [STOC'05] only address the low-dimensional regime, as their (1+ϵ)-approximation algorithm uses space exp(d). We design the first streaming algorithms that use space poly(d), and are thus suitable for a high dimension d.

We tackle this challenge of high dimension using two well-known approaches. The first one is via \emph{dimension reduction}, where we show that target dimension poly(ϵ−1) suffices for the Johnson-Lindenstrauss transform to preserve Max-Cut within factor (1±ϵ). This result extends the applicability of the prior work (algorithm with exp(d)-space) also to high dimension. The second approach is \emph{data reduction}, based on importance sampling. We implement this scheme in streaming by employing a randomly-shifted quadtree. While this is a well-known method to construct a tree embedding, a key feature of our algorithm is that the distortion O(dlogΔ) affects only the space requirement poly(ϵ−1dlogΔ), and not the approximation ratio 1+ϵ. These results are in line with the growing interest and recent results on streaming (and other) algorithms for high dimension.

Paper: https://arxiv.org/abs/2211.05293