Abstract
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(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).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
The \(\tilde {O}\) notation hides logarithmic factors.
The terms “type 1” and “type 2” are those of Even and Tarjan [10], who considered maximum flow problems on networks with unit capacities but no costs.
Most authors allow flows to be real-valued, but since our algorithms maintain integrality of flows it does no harm to restrict flows to be integral.
References
Ahuja, R.K., Goldberg, A.V., Orlin, J.B., Tarjan, R.E.: Finding Minimum-Cost Flows by Double Scaling. Math. Prog. 53, 243–266 (1992)
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows. In: Nemhauser, G.L., Rinnooy Kan, A.H.G., Todd, M.J. (eds.) Optimization. Handbooks in operations research and management science, vol. 1, pp. 211–369. North-Holland, Amsterdam (1989)
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall (1993)
Bertsekas, D.P.: Distributed asynchronous relaxation methods for linear network flow problems. Technical Report LIDS-p-1986, Lab. for decision systems M.I.T. (1986)
Bland, R.G., Jensen, D.L.: On the computational behavior of a polynomial-time network flow algorithm. Math. Prog. 54, 1–41 (1992)
Cherkassky, B.V., Goldberg, A.V., Silverstein, C.: Buckets, heaps, lists, and monotone priority queues. SIAM J. Comput. 28, 1326–1346 (1999)
Cohen, M.B., Madry, A., Sankowski, P., Vladu, A.: Negative-weight shortest paths and unit capacity minimum cost flow in Õ (m 10/7 w) time. In: SODA, pp. 752–771 (2017)
Daitch, S.I., Spielman, D.A.: Faster approximate lossy generalized flow via interior point algorithms. In: STOC, pp. 451–460 (2008)
Duan, R., Pettie, S., Su, H.: Scaling algorithms for approximate and exact maximum weight matching. CoRR, arXiv:1112.0790 (2011)
Even, S., Tarjan, R.E.: Network flow and testing graph connectivity. SIAM J. Comput. 4, 507–518 (1975)
Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. Assoc. Comput. Mach. 34, 596–615 (1987)
Gabow, H.N.: Scaling algorithms for network problems. J. Comp. Sys. Sci. 31, 148–168 (1985)
Gabow, H.N., Tarjan, R.E.: Faster Scaling Algorithms for Network Problems. SIAM J. Comput. 18, 1013–1036 (1989)
Goldberg, A.V.: Scaling algorithms for the shortest paths problem. SIAM J. Comput. 24, 494–504 (1995)
Goldberg, A.V., Kennedy, R.: Global Price Updates Help. SIAM J. Disc. Math. 10, 551–572 (1997)
Goldberg, A.V., Tarjan, R.E.: Finding minimum-cost circulations by successive approximation. Math. Oper. Res. 15, 430–466 (1990)
Hopcroft, J.E., Karp, R.M.: An n 5/2, Algorithm for Maximum Matching in Bipartite Graphs. SIAM J. Comput. 2, 225–231 (1973)
Karzanov, A.V.: O nakhozhdenii maksimal?nogo potoka v setyakh spetsial?nogo vida i nekotorykh prilozheniyakh. In: Matematicheskie Voprosy Upravleniya Proizvodstvom, volume 5. Moscow State University Press, Moscow, 1973. In Russian; title translation: On Finding Maximum Flows in Networks with Special Structure and Some Applications
Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Holt, Reinhart, and Winston, New York (1976)
Madry, A.: Navigating central path with electrical flows: From flows to matchings, and back. In: FOCS, pp. 253–262 (2013)
Orlin, J.B.: Faster strongly polynomial minimum cost flow algorithm. Oper. Res. 41, 338–350 (1993)
Ramshaw, L., Tarjan, R.: Endre a weight-scaling algorithm for min-cost imperfect matchings in bipartite graphs. In: FOCS, pp. 581–590 (2012)
Röck, H.: Scaling techniques for minimal cost network flows. In: Pape, U. (ed.) Discrete structures and algorithms, pp. 181–191. Carl Hansen, Münich (1980)
Tardos, É.: Strongly polynomial minimum cost circulation algorithm. Combinatorica 5(3), 247–255 (1985)
Acknowledgments
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).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Goldberg, A.V., Hed, S., Kaplan, H. et al. Minimum-Cost Flows in Unit-Capacity Networks. Theory Comput Syst 61, 987–1010 (2017). https://doi.org/10.1007/s00224-017-9776-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-017-9776-7