Aaron Sidford

collaborators

5 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^{I ¨ + o (1)}$ -time strongly polynomial tim…

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 $I^_{e}^{3} > 0$ governing whe…

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 I^µ^{- 1}$ -time algorithms for computing multiplicative $(1 - I^µ)$ -approximate solutions to multi-commodity flow problems with $k$ -commodities on $m$ -edge dire…

cs.DS2024

Entropy Regularization and Faster Decremental Matching in General Graphs

Jiale Chen, Aaron Sidford, Ta-Wei Tu

We provide an algorithm that maintains, against an adaptive adversary, a $(1 - ε)$ -approximate maximum matching in $n$ -node $m$ -edge general (not necessarily bipartite) und…

cs.DS2024

Matching Composition and Efficient Weight Reduction in Dynamic Matching

Aaron Bernstein, Jiale Chen, Aditi Dudeja +3

We consider the foundational problem of maintaining a $(1 - ε)$ -approximate maximum weight matching (MWM) in an $n$ -node dynamic graph undergoing edge insertions and deleti…