Streaming Euclidean Max-Cut: Dimension vs Data Reduction
share
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 ℝ^d, 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 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 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(ϵ^-1 dlogΔ), 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.
READ FULL TEXT