Finding Minimum-Cost Circulations by Canceling Negative Cycles

Andrew V. Goldberg, Robert E. Tarjan

Research output: Contribution to journalArticle

163 Scopus citations

Abstract

A classical algorithm for finding a minimum-cost circulation consists of repeatedly finding a residual cycle of negative cost and canceling it by pushing enough flow around the cycle to saturate an arc. We show that a judicious choice of cycles for canceling leads to a polynomial bound on the number of iterations in this algorithm. This gives a very simple strongly polynomial algorithm that uses no scaling. A variant of the algorithm that uses dynamic trees runs in Ο1989min{log(nC), m log n}) time on a network of n vertices, m arcs, and arc costs of maximum absolute value C. This bound is comparable to those of the fastest previously known algorithms.

Original languageEnglish (US)
Pages (from-to)873-886
Number of pages14
JournalJournal of the ACM (JACM)
Volume36
Issue number4
DOIs
StatePublished - Jan 10 1989

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Finding Minimum-Cost Circulations by Canceling Negative Cycles'. Together they form a unique fingerprint.

  • Cite this