Faster Sparse Minimum Cost Flow by Electrical Flow Localization

We give an $\tilde{O}(m^{3/2-1/762}\log(U+W))$ time algorithm for minimum cost flow with capacities bounded by $U$ and costs bounded by $W$. For sparse graphs with general capacities, this is the first algorithm to improve over the $\tilde{O}(m^{3/2}\log^{O(1)}(U+W))$ running time obtained by an appropriate instantiation of an interior point method [Daitch-Spielman, 2008]. Our approach is extending the framework put forth in [Gao-Liu-Peng, 2021] for computing the maximum flow in graphs with large capacities and, in particular, demonstrates how to reduce the problem of computing an electrical flow with general demands to the same problem on a sublinear-sized set of vertices—even if the demand is supported on the entire graph. Along the way, we develop new machinery to assess the importance of the graph's edges at each phase of the interior point method optimization process. This capability relies on establishing a new connections between the electrical flows arising inside that optimization process and vertex distances in the corresponding effective resistance metric.

Authors

• Kyriakos Axiotis
• Aleksander Madry
• Adrian Vladu

Keywords

• Resistance
• Measurement
• Location awareness
• Computer science
• Costs
• Machinery
• Optimization
• Electric Flow
• Minimum Cost Flow
• Running Time
• Generation Capacity
• Maximum Flow
• Demand Generation
• Interior Point Method
• Minimum Flow
• Sparse Graph
• Flow Graph
• Data Structure
• Random Walk
• Minimization Problem
• Flow Values
• Flow Problem
• Congested
• Goal Of This Section
• Flow Algorithm
• Duality Gap
• Central Path
• Schur Complement
• graph algorithms
• electrical flows