Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs
share
We present an m^11/8+o(1)log W-time algorithm for solving the minimum cost flow problem in graphs with unit capacity, where W is the absolute maximum weight of an edge in the graph. For sparse graphs, this improves over the best known running time for this problem and, by well-known reductions, also implies improved running times for the shortest path problem with negative weights, minimum cost bipartite b-matching when b_1 = O(m), and recovers the running time of the currently fastest algorithm for maximum flow in graphs with unit capacities (Liu-Sidford). Our algorithm relies on developing an interior point method–based framework which acts on the space of circulations in the underlying graph. From the combinatorial point of view, this framework can be viewed as iteratively improving the cost of a suboptimal solution by pushing flow around circulations. These circulations are derived by computing a regularized version of the standard Newton step, which can be done efficiently due to recent developments on computing ℓ_p-norm minimizing flows (Kyng-Peng-Sachdeva-Wang). We obtain our faster algorithm by combining this approach with a customized preconditioning method, which aims to ensure that the graph on which these circulations are computed has sufficiently large conductance.
READ FULL TEXT