Minimum-Cost Flows in Unit-Capacity Networks
Minimum-Cost Flows in Unit-Capacity Networks
复制标题
单位容量网络中的最小成本流
DOI：
10.1007/s00224-017-9776-7
复制
发表时间：
2017
影响因子：
0.5
通讯作者：
R. Tarjan
中科院分区：
文献类型：
--
作者：
A. Goldberg;Sagi Hed;Haim Kaplan;R. Tarjan
我们考虑组合算法的最小费用流问题的网络与单位容量，和特殊情况下的问题。从历史上看，研究人员已经开发出利用单位容量的专用算法。与此相反，对于最大流问题，经典的阻塞流和推重标记算法的一般情况下，也有最好的边界已知的特殊情况下的单位容量。在本文中，我们表明，经典的阻塞流推重新标记成本缩放算法的Goldberg和Tarjan（数学。Res. 15，430-466，1990）对于一般的最小费用流问题也获得了单位容量问题的最佳已知界。我们还开发了一种循环取消算法，扩展了Goldberg的最短路径算法（Goldberg SIAM J. 24，494-504，1995）到最小成本、单位容量流问题。最后，我们联合收割机我们的想法，以获得一个算法，解决了最小成本二分匹配问题的O（r1/2 mlogC）$O（r^{1/2} m \log C）$时间，其中m是边的数量，C是最大的弧成本（假设大于1），和r是顶点二分的小边的顶点数。该结果推广（并简化）了Duan等人（2011）的结果，并解决了Ramshaw和Tarjan（2012）的一个开放问题。
We consider combinatorial algorithms for the minimum-cost flow problem on networks with unit capacities, and special cases of the problem. Historically, researchers have developed special-purpose algorithms that exploit unit capacities. In contrast, for the maximum flow problem, the classical blocking flow and push-relabel algorithms for the general case also have the best bounds known for the special case of unit capacities. In this paper we show that the classical blocking flow push-relabel cost-scaling algorithms of Goldberg and Tarjan (Math. Oper. Res. 15, 430–466, 1990) for general minimum-cost flow problems achieve the best known bounds for unit-capacity problems as well. We also develop a cycle-canceling algorithm that extends Goldberg’s shortest path algorithm (Goldberg SIAM J. Comput. 24, 494–504, 1995) to minimum-cost, unit-capacity flow problems. Finally, we combine our ideas to obtain an algorithm that solves the minimum-cost bipartite matching problem in O(r1/2mlogC)$O(r^{1/2} m \log C)$ time, where m is the number of edges, C is the largest arc cost (assumed to be greater than 1), and r is the number of vertices on the small side of the vertex bipartition. This result generalizes (and simplifies) a result of Duan et al. (2011) and solves an open problem of Ramshaw and Tarjan (2012).