Faster energy maximization for faster maximum flow
Faster energy maximization for faster maximum flow
复制标题
DOI：
10.1145/3357713.3384247
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Yang P. Liu;Aaron Sidford
中科院分区：
文献类型：
--
作者：
Yang P. Liu;Aaron Sidford
本文给出了一个算法，该算法对任意一个容量不超过U的m边n点有向图，以很高的概率在m11/8+o（1）U1/4时间内计算任意顶点s和t的最大s-t流.当图不是太密集或容量很大时，这个运行时间比之前的最佳值O（m 10/7 U 1/7）（Munday dry 2016）、O（m n logU）（Lee Sidford 2014）和O（mn）（Orlin 2013）有所改进。我们实现这一结果，利用最近的进展，解决无向流问题的图。我们表明，在最大流框架中（Mingdry 2016），优化最大化能量所需的中心路径扰动量，从而减少拥塞的问题可以有效地减少到平滑的22-bnp流优化问题，该问题可以通过最近的工作近似解决（Kyng，Peng，Sachdeva，Wang 2019）。利用这个新的原语，我们提供了一种新的最大流内点方法，具有更快的收敛速度和更简单的分析，不再需要像以前的方法那样涉及能量的全局势函数（Mingdry 2013，Mingdry 2016）。
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. 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 ℓ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 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).