In this paper we provide an algorithm which given any m-edge n-vertex directed graph with integer capacities at most U computes a maximum s-t flow for any vertices s and t in m^{4/3+o(1)}U^{1/3} time. This improves upon the previous best running times of m^{11/8+o(1)}U^{1/4} (Liu Sidford 2019), O(m n \log U) (Lee Sidford 2014), and O(mn) (Orlin 2013) when the graph is not too dense or has large capacities. To achieve the results this paper we build upon previous algorithmic approaches to maximum flow based on interior point methods (IPMs). In particular, we overcome a key bottleneck of previous IPMs applying to maxflow (Madry 2013, Madry 2016, Cohen M\k{a Liu Sidford 2019 , Axiotis M\k{a ), which make progress by maximizing the energy of local \ell_2 norm minimizing electric flows. We generalize this approach and instead maximize the divergence of flows which minimize the Bregman divergence distance with respect to the weighted logarithmic barrier. This allows our algorithm to depend on the \ell _\infty norm as opposed to the \ell_4 norm when bounding the amount of weight perturbation needed . Further, we show that smoothed \ell_2-\ell_p flows (Kyng, Peng, Sachdeva, Wang 2019), which we previously used to efficiently maximize energy (Liu Sidford 2019), can also be used to efficiently maximize divergence, thereby yielding our desired runtimes. We believe both this generalized view of energy maximization and generalized flow solvers we develop may be of further interest.
In this paper we provide an algorithm which given any m-edge n-vertex directed graph with integer capacities at most U computes a maximum s-t flow for any vertices s and t in m^{4/3+o(1)}U^{1/3} time. This improves upon the previous best running times of m^{11/8+o(1)}U^{1/4} (Liu Sidford 2019), O(m n \log U) (Lee Sidford 2014), and O(mn) (Orlin 2013) when the graph is not too dense or has large capacities. To achieve the results this paper we build upon previous algorithmic approaches to maximum flow based on interior point methods (IPMs). In particular, we overcome a key bottleneck of previous advances in IPMs for maxflow (Madry 2013, Madry 2016, Liu Sidford 2019 ), which make progress by maximizing the energy of local \ell_2 norm minimizing electric flows. We generalize this approach and instead maximize the divergence of flows which minimize the Bregman divergence distance with respect to the weighted logarithmic barrier. This allows our algorithm to avoid dependencies on the \ell _4 norm that appear in other IPM frameworks (e.g. Cohen M\k{a . Further, we show that smoothed \ell_2-\ell_p flows (Kyng, Peng, Sachdeva, Wang 2019), which we previously used to efficiently maximize energy (Liu Sidford 2019), can also be used to efficiently maximize divergence, thereby yielding our desired runtimes. We believe both this generalized view of energy maximization and generalized flow solvers we develop may be of further interest.
R
IPMs applying to
advances in IPMs for
D
Cohen M\k{a
D
, Axiotis M\k{a
R
depend
avoid dependencies
R
_\infty norm as opposed to the \ell_4 norm when bounding the amount of weight perturbation needed
_4 norm that appear in other IPM frameworks (e.g. Cohen M\k{a