{"ID":2859657,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.04435","arxiv_id":"2510.04435","title":"Streaming Max-Cut in General Metrics","abstract":"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 \\emph{general metric spaces} with access to distance oracles. We give a $(1 + ε)$-approximate algorithm for estimating the Max-Cut value in \\emph{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 \\emph{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.","short_abstract":"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 \\emph{general metric spaces} with access to distance oracles. We give a $(1 + ε)$-approximate algorithm for estimating the Max-Cut value in \\emph{slid...","url_abs":"https://arxiv.org/abs/2510.04435","url_pdf":"https://arxiv.org/pdf/2510.04435v2","authors":"[\"Shaofeng H. -C. Jiang\",\"Pan Peng\",\"Haoze Wang\"]","published":"2025-10-06T02:06:09Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}