Minimum-Cost Flows in Unit-Capacity Networks

Andrew V. Goldberg, Sagi Hed, Haim Kaplan, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

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

Original languageEnglish (US)
Pages (from-to)987-1010
Number of pages24
JournalTheory of Computing Systems
Volume61
Issue number4
DOIs
StatePublished - Nov 1 2017

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Keywords

  • Algorithms
  • Assignment problem
  • Bipartite matching
  • Minimum-cost flows

Fingerprint

Dive into the research topics of 'Minimum-Cost Flows in Unit-Capacity Networks'. Together they form a unique fingerprint.

Cite this