2025/10/06 by Shaofeng H. -C. Jiang, Peng Pan, Jiang, Shaofeng H. -C. +2
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Stochastic Gradient Optimization Techniques #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2510.04435
Max-Cut is a fundamental combinatorial optimization problem that has been studied in various computational settings. We initiate the study of its streaming complexity in general metric spaces with access to distance oracles. We give a (1 + ε)-approximate algorithm for estimating the Max-Cut value in sliding-window streams using only poly-logarithmic space. This is the first sliding-window algorithm for Max-Cut even in Euclidean spaces, and it matches a known insertion-only space bound in the special case of Euclidean spaces [Chen, Jiang, Krauthgamer, STOC'23]. In sharp contrast, we give a \poly(n)-space lower bound in the dynamic streaming setting. This yields a separation from the Euclidean case, where the polylogarithmic-space (1+ε)-approximation extends to dynamic streams. On the technical side, our sliding-window algorithm builds on the smooth histogram framework of [Braverman and Ostrovsky, SICOMP'10]. To make this framework applicable, we establish the first smoothness bound for metric Max-Cut. Moreover, we develop a streaming algorithm for metric Max-Cut in insertion-only streams, whose key ingredient is a new metric reservoir sampling technique.