Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m10/7 log W) Time (Extended Abstract)
Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m10/7 log W) Time (Extended Abstract)
复制标题
Õ (m10/7 log W) 时间内的负权最短路径和单位容量最小成本流（扩展摘要）
DOI：
10.1137/1.9781611974782.48
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Adrian Vladu
中科院分区：
文献类型：
--
作者：
Michael B. Cohen;A. Madry;P. Sankowski;Adrian Vladu
本文研究了一类加权图上的组合优化问题：负权最短路问题、加权完美二部匹配问题、单位容量最小费用最大流问题和加权完美二部$B$-匹配问题，并假设$\Vertb\Vert_1 =O（m）$。我们证明了这四个问题中的每一个都可以在$\tilde{O}（m^{10/7}\log W）$时间内解决，其中$W$是图中边的绝对最大权重，这是25年来多项式稀疏图时间复杂度的第一次改进。
在高层次上，我们的算法建立在Madry（FOCS 2013）开发的基于通道点方法的框架上，用于解决单位容量最大流问题。我们开发了一个精致的方法来分析这个框架，以及提供新的变种的基础预处理和扰动技术。因此，我们能够扩展整个基于邻域点方法的方法，使其适用于加权图制度。
In this paper, we study a set of combinatorial optimization problems on weighted graphs: the shortest path problem with negative weights, the weighted perfect bipartite matching problem, the unit-capacity minimum-cost maximum flow problem and the weighted perfect bipartite $b$-matching problem under the assumption that $\Vert b\Vert_1=O(m)$. We show that each one of these four problems can be solved in $\tilde{O}(m^{10/7}\log W)$ time, where $W$ is the absolute maximum weight of an edge in the graph, which gives the first in over 25 years polynomial improvement in their sparse-graph time complexity.
At a high level, our algorithms build on the interior-point method-based framework developed by Madry (FOCS 2013) for solving unit-capacity maximum flow problem. We develop a refined way to analyze this framework, as well as provide new variants of the underlying preconditioning and perturbation techniques. Consequently, we are able to extend the whole interior-point method-based approach to make it applicable in the weighted graph regime.