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).

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

VL - 61

SP - 987

EP - 1010

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 4

ER -