### 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 language | English (US) |
---|---|

Pages (from-to) | 873-886 |

Number of pages | 14 |

Journal | Journal of the ACM (JACM) |

Volume | 36 |

Issue number | 4 |

DOIs | |

State | Published - 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

Goldberg, A. V., & Tarjan, R. E. (1989). Finding Minimum-Cost Circulations by Canceling Negative Cycles.

*Journal of the ACM (JACM)*,*36*(4), 873-886. https://doi.org/10.1145/76359.76368