## Abstract

Several researchers have recently developed new techniques that give fast algorithms for the minimum-cost flow problem. In this paper we combine several of these techniques to yield an algorithm running in O(nm(log log U) log(nC)) time on networks with n vertices, m edges, maximum arc capacity U, and maximum arc cost magnitude C. The major techniques used are the capacity-scaling approach of Edmonds and Karp, the excess-scaling approach of Ahuja and Orlin, the cost-scaling approach of Goldberg and Tarjan, and the dynamic tree data structure of Sleator and Tarjan. For nonsparse graphs with large maximum arc capacity, we obtain a similar but slightly better bound. We also obtain a slightly better bound for the (noncapacitated) transportation problem. In addition, we discuss a capacity-bounding approach to the minimum-cost flow problem.

Original language | English (US) |
---|---|

Pages (from-to) | 243-266 |

Number of pages | 24 |

Journal | Mathematical Programming |

Volume | 53 |

Issue number | 1-3 |

DOIs | |

State | Published - Jan 1992 |

## All Science Journal Classification (ASJC) codes

- Software
- General Mathematics

## Keywords

- Minimum-cost flows
- dynamic trees
- minimum-cost circulations
- scaling
- transportation problem