{"ID":2824531,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.22729","arxiv_id":"2512.22729","title":"Half-Approximating Maximum Dicut in the Streaming Setting","abstract":"We study streaming algorithms for the maximum directed cut problem. The edges of an $n$-vertex directed graph arrive one by one in an arbitrary order, and the goal is to estimate the value of the maximum directed cut using a single pass and small space. With $O(n)$ space, a $(1-\\varepsilon)$-approximation can be trivially obtained for any fixed $\\varepsilon \u003e 0$ using additive cut sparsifiers. The question that has attracted significant attention in the literature is the best approximation achievable by algorithms that use truly sublinear (i.e., $n^{1-Ω(1)}$) space. A lower bound of Kapralov and Krachun (STOC'19) implies .5-approximation is the best one can hope for. The current best algorithm for general graphs obtains a .485-approximation due to the work of Saxena, Singer, Sudan, and Velusamy (FOCS'23). The same authors later obtained a $(1/2-\\varepsilon)$-approximation, assuming that the graph is constant-degree (SODA'25). In this paper, we show that for any $\\varepsilon \u003e 0$, a $(1/2-\\varepsilon)$-approximation of maximum dicut value can be obtained with $n^{1-Ω_\\varepsilon(1)}$ space in *general graphs*. This shows that the lower bound of Kapralov and Krachun is generally tight, settling the approximation complexity of this fundamental problem. The key to our result is a careful analysis of how correlation propagates among high- and low-degree vertices, when simulating a suitable local algorithm.","short_abstract":"We study streaming algorithms for the maximum directed cut problem. The edges of an $n$-vertex directed graph arrive one by one in an arbitrary order, and the goal is to estimate the value of the maximum directed cut using a single pass and small space. With $O(n)$ space, a $(1-\\varepsilon)$-approximation can be trivia...","url_abs":"https://arxiv.org/abs/2512.22729","url_pdf":"https://arxiv.org/pdf/2512.22729v2","authors":"[\"Amir Azarmehr\",\"Soheil Behnezhad\",\"Shane Ferrante\",\"Mohammad Saneian\"]","published":"2025-12-28T00:07:20Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}