Streaming Euclidean Max-Cut: Dimension vs Data Reduction
Xiaoyu Chen, Shaofeng H.-C. Jiang, Robert Krauthgamer · 2023
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 ℝd, in the model of dynamic geometric streams, where the input X ⊆ [Δ]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).