7 papers
Near-Optimal Parallel -Matrix Scaling
Chih-Hung Liu, Aaron Sidford, Ta-Wei Tu
In this paper we consider the problem of computing a positive diagonal scaling of a symmetric -matrix so that all row and column sums are . We provide a poly-log…
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 -node -arc networks. Our results imply an -time strongly polynomial time…
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 -edge -node directed graph and each edge has a loss factor governing whet…
Accelerated Approximate Optimization of Multi-Commodity Flows on Directed Graphs
Li Chen, Andrei Graur, Aaron Sidford
We provide -time algorithms for computing multiplicative -approximate solutions to multi-commodity flow problems with -commodities on -edge direct…
Matching Composition and Efficient Weight Reduction in Dynamic Matching
Aaron Bernstein, Jiale Chen, Aditi Dudeja +3
We consider the foundational problem of maintaining a -approximate maximum weight matching (MWM) in an -node dynamic graph undergoing edge insertions and deleti…
Eulerian Graph Sparsification by Effective Resistance Decomposition
Arun Jambulapati, Sushant Sachdeva, Aaron Sidford +2
We provide an algorithm that, given an -vertex -edge Eulerian graph with polynomially bounded weights, computes an -edge $\vare…
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 -approximate maximum matching in -node -edge general (not necessarily bipartite) und…