TY - JOUR
T1 - Minimum-Cost Flows in Unit-Capacity Networks
AU - Goldberg, Andrew V.
AU - Hed, Sagi
AU - Kaplan, Haim
AU - Tarjan, Robert E.
N1 - Funding Information:
Sagi Hed research supported by the Israel Science Foundation grants no. 822-10 and 1841/14, and the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11).
Funding Information:
Haim Kaplan research supported by the Israel Science Foundation grants no. 822-10 and 1841/14, the German-Israeli Foundation for Scientific Research Development (GIF) grant no. 1161/2011, the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11).
Funding Information:
We thank an anonymous reviewer for a significant simplification of Step 4 of the refinement algorithm in Section?4.1. Part of the work was done while Andrew V. Goldberg was at Microsoft Research. Sagi Hed research supported by the Israel Science Foundation grants no. 822-10 and 1841/14, and the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11). Haim Kaplan research supported by the Israel Science Foundation grants no. 822-10 and 1841/14, the German-Israeli Foundation for Scientific Research Development (GIF) grant no. 1161/2011, the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11).
Publisher Copyright:
© 2017, Springer Science+Business Media New York.
PY - 2017/11/1
Y1 - 2017/11/1
N2 - 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 / 2mlog 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).
AB - 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 / 2mlog 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).
KW - Algorithms
KW - Assignment problem
KW - Bipartite matching
KW - Minimum-cost flows
UR - http://www.scopus.com/inward/record.url?scp=85019230683&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85019230683&partnerID=8YFLogxK
U2 - 10.1007/s00224-017-9776-7
DO - 10.1007/s00224-017-9776-7
M3 - Article
AN - SCOPUS:85019230683
SN - 1432-4350
VL - 61
SP - 987
EP - 1010
JO - Theory of Computing Systems
JF - Theory of Computing Systems
IS - 4
ER -