Faster Energy Maximization for Faster Maximum Flow

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 m11/8+o(1)U1/4 time with high probability. This running time improves upon the previous best of tildeO(m10/7 U1/7) (Mkadry 2016), tildeO(m √n log U) (Lee Sidford 2014), and O(mn) (Orlin 2013) when the graph is not too dense or has large capacities. We achieve this result by leveraging recent advances in solving undirected flow problems on graphs. We show that in the maximum flow framework of (Mkadry 2016) the problem of optimizing the amount of perturbation of the central path needed to maximize energy and thereby reduce congestion can be efficiently reduced to a smoothed ℓ2-ℓp flow optimization problem, which can be solved approximately via recent work (Kyng, Peng, Sachdeva, Wang 2019). Leveraging this new primitive, we provide a new long-step interior point method for maximum flow with faster convergence and simpler analysis that no longer needs global potential functions involving energy as in previous methods (Mkadry 2013, Mkadry 2016).