Aaron Sidford

collaborators

3 papers

cs.DS2025

From Incremental Transitive Cover to Strongly Polynomial Maximum Flow

Daniel Dadush, James B. Orlin, Aaron Sidford +1

We provide faster strongly polynomial time algorithms solving maximum flow in structured $n$ -node $m$ -arc networks. Our results imply an $n^{ω + o (1)}$ -time strongly polynomial time…

cs.DS2025

Generalized Flow in Nearly-linear Time on Moderately Dense Graphs

Shunhua Jiang, Michael Kapralov, Lawrence Li +1

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} > 0$ governing whet…

cs.DS2025

Accelerated Approximate Optimization of Multi-Commodity Flows on Directed Graphs

Li Chen, Andrei Graur, Aaron Sidford

We provide $m^{1 + o (1)} k ε^{- 1}$ -time algorithms for computing multiplicative $(1 - ε)$ -approximate solutions to multi-commodity flow problems with $k$ -commodities on $m$ -edge direct…