Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs
Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs
复制标题
DOI：
10.1109/focs46700.2020.00018
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
Kyriakos Axiotis;Aleksander Mkadry;Adrian Vladu
中科院分区：
文献类型：
--
作者：
Kyriakos Axiotis;Aleksander Mkadry;Adrian Vladu
给出了一个求解单位容量图中最小费用流问题的$m^{4/3+o(1)}\log W$-time算法，其中$W$是任意边权的最大绝对值。对于稀疏图，这比这个问题的最佳运行时间有所改善，并且通过众所周知的简化，还意味着具有负权的最短路径问题的运行时间得到了改善，当$\Vert b\Vert_{1}=O(M)$时，最小代价二部$b$匹配，并且恢复了当前求解具有单位容量的图的最大流的最快算法的运行时间(Liu-Sidford，2020)。我们的算法依赖于开发一个基于内点方法的框架，该框架作用于底层图中的循环空间。从组合的观点来看，这个框架可以被视为通过推动循环周围的流动来迭代地改善次优解的成本。这些循环是通过计算标准牛顿步长的正则化版本来推导的，该标准牛顿步长的部分灵感来自于先前关于单位容量最大流问题的工作(Liu-Sidford，2019)，并随后基于该问题的最新进展(Liu-Sidford，2020)进行了改进。然后，使用最近关于$\ell_{p}$-范数最小化流的工作(Kyng-Peng-Sachdeva-Wang，2019年)，可以有效地计算得到的步长问题。我们通过将这种新的步长原语与一种定制的预条件方法相结合来获得更快的算法，该方法旨在确保计算这些循环的图具有足够大的电导。
We present an $m^{4/3+o(1)}\log W$-time algorithm for solving the minimum cost flow problem in graphs with unit capacity, where $W$ is the maximum absolute value of any edge weight. For sparse graphs, this improves over the best known running time for this problem and, by well-known reductions, also implies improved running times for the shortest path problem with negative weights, minimum cost bipartite $b$-matching when $\Vert b\Vert_{1}=O(m)$, and recovers the running time of the currently fastest algorithm for maximum flow in graphs with unit capacities (Liu-Sidford, 2020). Our algorithm relies on developing an interior point method-based framework which acts on the space of circulations in the underlying graph. From the combinatorial point of view, this framework can be viewed as iteratively improving the cost of a suboptimal solution by pushing flow around circulations. These circulations are derived by computing a regularized version of the standard Newton step, which is partially inspired by previous work on the unit-capacity maximum flow problem (Liu-Sidford, 2019), and subsequently refined based on the very recent progress on this problem (Liu-Sidford, 2020). The resulting step problem can then be computed efficiently using the recent work on $\ell_{p}$-norm minimizing flows (Kyng-Peng-Sachdeva-Wang, 2019). We obtain our faster algorithm by combining this new step primitive with a customized preconditioning method, which aims to ensure that the graph on which these circulations are computed has sufficiently large conductance.