
























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 $\tilde{O}(m^{10/7} U^{1/7})$ (Mądry 2016), $\tilde{O}(m \sqrt{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 (Mądry 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 $\ell_2$-$\ell_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 (Mądry 2013, Mądry 2016).
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。