论文标题
潜在的还原灵感算法，用于几乎$ \ wideTilde {o}（m^{4/3}）$ time的精确最大流量
A Potential Reduction Inspired Algorithm for Exact Max Flow in Almost $\widetilde{O}(m^{4/3})$ Time
论文作者
论文摘要
我们提出了一种用于计算$ s $ - $ t $最大流量的算法，以$ \ widetilde {o}（m^{4/3+o（1）} u^{1/3}）$时间。我们的算法灵感来自线性编程的潜在减少内点方法。我们采取的步骤不使用缩放梯度/牛顿的步骤，而是采取步骤，该步骤可最大程度地减少潜在值的减小，而要在中心路径上推进一定数量的一定量，可以有效地计算出一定数量。这使我们能够在拥塞向量上仅取决于$ \ ell_ \ infty $ norm界（而不是以前的作品所需的$ \ ell_4 $ norm），并以$ o（\ sqrt {m}）$ itererations运行。为了通过在$ \ ell_ \ infty $ norm上建立更严格的界限来改善迭代次数，然后我们考虑Madry \ cite {M13，M16，CMSV17}的加权中心路径框架和Liu-Sidford \ cite \ cite {ls20}。我们考虑找到权重，而不是改变权重以最大程度地提高能量，从而最大程度地减少潜在值。最后，类似于找到可以通过\ cite {ls20}完成的权重的权重，可以通过平滑的$ \ ell_2 $ - $ \ ell_p $ norm flow问题\ cite {kpsw19}完成我们的algorithm的迭代精炼框架来解决此问题。我们认为，我们潜在的基于还原的观点提供了一种多功能框架，该框架可能会导致最大流量的更快算法。
We present an algorithm for computing $s$-$t$ maximum flows in directed graphs in $\widetilde{O}(m^{4/3+o(1)}U^{1/3})$ time. Our algorithm is inspired by potential reduction interior point methods for linear programming. Instead of using scaled gradient/Newton steps of a potential function, we take the step which maximizes the decrease in the potential value subject to advancing a certain amount on the central path, which can be efficiently computed. This allows us to trace the central path with our progress depending only $\ell_\infty$ norm bounds on the congestion vector (as opposed to the $\ell_4$ norm required by previous works) and runs in $O(\sqrt{m})$ iterations. To improve the number of iterations by establishing tighter bounds on the $\ell_\infty$ norm, we then consider the weighted central path framework of Madry \cite{M13,M16,CMSV17} and Liu-Sidford \cite{LS20}. Instead of changing weights to maximize energy, we consider finding weights which maximize the maximum decrease in potential value. Finally, similar to finding weights which maximize energy as done in \cite{LS20} this problem can be solved by the iterative refinement framework for smoothed $\ell_2$-$\ell_p$ norm flow problems \cite{KPSW19} completing our algorithm. We believe our potential reduction based viewpoint provides a versatile framework which may lead to faster algorithms for max flow.
