论文标题
更快的发散最大化速度更快的最大流量
Faster Divergence Maximization for Faster Maximum Flow
论文作者
论文摘要
在本文中，我们提供了一种算法，该算法给出了任何$ M $ -EDGE $ n $ vertex有向图，最多$ u $ $ u $计算的最大$ s $ -s $ t $流量用于任何Vertices $ s $和$ s $ s $和$ t $ in $ m^{4/3+o（1/3+o（1）这可以改善$ m^{11/8+o（1）} u^{1/4} $（liu sidford 2019），$ \ tilde {o}（m \ sqrt {n} \ log u）$（Lee Sidford 2014）和$ O（Mn）$（or Grape 2013）ns of ynes n ynes nes nes n ynes n yne n ynes n ynes n ynes n n ynes Is n y n y n ynes n is yne as Grand，n is ynes Is n ynes Is n y n ynes IS n ynes IS yne n ynes n is n ynes， 为了达到结果，我们基于以前基于内部方法（IPM）的最大流量的算法方法的构建。特别是，我们克服了MaxFlow IPMS先前进步的关键瓶颈（MąDry2013，MąDry2016，Liu Sidford 2019），这通过最大化本地$ \ ell_2 $ norm norm norm norm最小化电流而取得了进步。我们概括了这种方法，并最大程度地提高了流动的差异，从而使布雷格曼的差异距离相对于加权对数屏障。这允许我们的算法避免对其他IPM框架中出现的$ \ ell_4 $ norm的依赖性（例如，CohenMąDrySankowski Vladu 2017，AxiotismądryVladu 2020）。此外，我们表明，流畅的$ \ ell_2 $ - $ \ ell_p $ flow（Kyng，Peng，Sachdeva，Wang 2019），我们以前用来有效地最大化能量（Liu Sidford 2019），也可以用来有效地最大程度地发挥分歧，从而产生我们所期望的运行时。我们认为，这种对能量最大化的广义观点和我们开发的广义流求解器可能会进一步引起人们的关注。
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), $\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. 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 (Mądry 2013, Mądry 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ądry Sankowski Vladu 2017, Axiotis Mądry Vladu 2020). 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.
