{"ID":2852896,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.17740","arxiv_id":"2510.17740","title":"Generalized Flow in Nearly-linear Time on Moderately Dense Graphs","abstract":"In this paper we consider generalized flow problems where there is an $m$-edge $n$-node directed graph $G = (V,E)$ and each edge $e \\in E$ has a loss factor $γ_e \u003e0$ governing whether the flow is increased or decreased as it crosses edge $e$. We provide a randomized $\\tilde{O}( (m + n^{1.5}) \\cdot \\mathrm{polylog}(\\frac{W}δ))$ time algorithm for solving the generalized maximum flow and generalized minimum cost flow problems in this setting where $δ$ is the target accuracy and $W$ is the maximum of all costs, capacities, and loss factors and their inverses. This improves upon the previous state-of-the-art $\\tilde{O}(m \\sqrt{n} \\cdot \\log^2(\\frac{W}δ) )$ time algorithm, obtained by combining the algorithm of [Daitch-Spielman, 2008] with techniques from [Lee-Sidford, 2014]. To obtain this result we provide new dynamic data structures and spectral results regarding the matrices associated to generalized flows and apply them through the interior point method framework of [Brand-Lee-Liu-Saranurak-Sidford-Song-Wang, 2021].","short_abstract":"In this paper we consider generalized flow problems where there is an $m$-edge $n$-node directed graph $G = (V,E)$ and each edge $e \\in E$ has a loss factor $γ_e \u003e0$ governing whether the flow is increased or decreased as it crosses edge $e$. We provide a randomized $\\tilde{O}( (m + n^{1.5}) \\cdot \\mathrm{polylog}(\\fra...","url_abs":"https://arxiv.org/abs/2510.17740","url_pdf":"https://arxiv.org/pdf/2510.17740v1","authors":"[\"Shunhua Jiang\",\"Michael Kapralov\",\"Lawrence Li\",\"Aaron Sidford\"]","published":"2025-10-20T16:51:00Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}