Faster energy maximization for faster maximum flow
Yang P. Liu, Aaron Sidford · 2020
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 11/8+o(1) U 1/4 time with high probability. This running time improves upon the previous best of Õ(m 10/7 U 1/7) (Mądry 2016), Õ(m √n logU) (Lee Sidford 2014), and O(mn) (Orlin 2013) when the graph is not too dense or has large capacities.