Finding minimum-cost circulations by canceling negative cycles

Andrew V. Goldberg, Robert Endre Tarjan

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

14 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 O(nm(log n) mini{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)
Title of host publicationProceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC 1988
PublisherAssociation for Computing Machinery
Pages388-397
Number of pages10
ISBN (Print)0897912640, 9780897912648
DOIs
StatePublished - Jan 1 1988
Event20th Annual ACM Symposium on Theory of Computing, STOC 1988 - Chicago, IL, United States
Duration: May 2 1988May 4 1988

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other20th Annual ACM Symposium on Theory of Computing, STOC 1988
CountryUnited States
CityChicago, IL
Period5/2/885/4/88

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Finding minimum-cost circulations by canceling negative cycles'. Together they form a unique fingerprint.

Cite this