Minimum cost flows in graphs with unit capacities

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

We consider the minimum cost flow problem on graphs with unit capacities and its special cases. In previous studies, special purpose algorithms exploiting the fact that capacities are one have been developed. In contrast, for maximum flow with unit capacities, the best bounds are proven for slight modifications of classical blocking flow and push-relabel algorithms. In this paper we show that the classical cost scaling algorithms of Goldberg and Tarjan (for general integer capacities) applied to a problem with unit capacities achieve or improve the best known bounds. For weighted bipartite matching we establish a bound of O(√rmlog C) on a slight variation of this algorithm. Here r is the size of the smaller side of the bipartite graph, m is the number of edges, and C is the largest absolute value of an arc-cost. This simplifies a result of [Duan et al. 2011] and improves the bound, answering an open question of [Tarjan and Ramshaw 2012]. For graphs with unit vertex capacities we establish a novel O(√nmlog(nC)) bound. We also give the first cycle canceling algorithm for minimum cost flow with unit capacities. The algorithm naturally generalizes the single source shortest path algorithm of [Goldberg 1995].

Original languageEnglish (US)
Title of host publication32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015
EditorsErnst W. Mayr, Nicolas Ollinger
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages406-419
Number of pages14
ISBN (Electronic)9783939897781
DOIs
StatePublished - Feb 1 2015
Event32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015 - Garching, Germany
Duration: Mar 4 2015Mar 7 2015

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume30
ISSN (Print)1868-8969

Other

Other32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015
CountryGermany
CityGarching
Period3/4/153/7/15

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Bipartite matching
  • Cost scaling
  • Minimum cost flow
  • Unit capacity

Fingerprint Dive into the research topics of 'Minimum cost flows in graphs with unit capacities'. Together they form a unique fingerprint.

  • Cite this

    Goldberg, A. V., Kaplan, H., Hed, S., & Tarjan, R. E. (2015). Minimum cost flows in graphs with unit capacities. In E. W. Mayr, & N. Ollinger (Eds.), 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015 (pp. 406-419). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 30). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.STACS.2015.406