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 \mathit{b}-matching when \|\mathit{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 \ell_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.
We present an m^{ 4 / 3 +o(1)}\log W-time algorithm for solving the minimum cost flow problem in graphs with unit capacity, where W is the maximum absolute value of any edge weight . 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 \mathit{b}-matching when \|\mathit{b}\|_1 = O(m), and recovers the running time of the currently fastest algorithm for maximum flow in graphs with unit capacities (Liu-Sidford , 2020 ). 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 is partially inspired by previous work on the unit-capacity maximum flow problem (Liu-Sidford, 2019), and subsequently refined based on the very recent progress on this problem (Liu-Sidford, 2020). The resulting step problem can then be computed efficiently using the recent work on \ell_p-norm minimizing flows (Kyng-Peng-Sachdeva-Wang , 2019 ). We obtain our faster algorithm by combining this new step primitive with a customized preconditioning method, which aims to ensure that the graph on which these circulations are computed has sufficiently large conductance.
R
11
4
R
8
3
R
absolute maximum weight of an edge in the graph
maximum absolute value of any edge weight
A
, 2020
R
method--based
method-based
R
can be done efficiently due to recent developments on computing
is partially inspired by previous work on the unit-capacity maximum flow problem (Liu-Sidford, 2019), and subsequently refined based on the very recent progress on this problem (Liu-Sidford, 2020). The resulting step problem can then be computed efficiently using the recent work on
A
, 2019
R
approach
new step primitive