## Abstract

This paper presents algorithms for the assignment problem, the transportation problem, and the minimum-cost flow problem of operations research. The algorithms find a minimum-cost solution, yet run in time close to the best-known bounds for the corresponding problems without costs. For example, the assignment problem (equivalently, minimum-cost matching in a bipartite graph) can be solved in O(√nm log(nN)) time, where n, m, and N denote the number of vertices, number of edges, and largest magnitude of a cost; costs are assumed to be integral. The algorithms work by scaling. In each scaled problem an approximate optimum solution is found, rather than an exact optimum.

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

Pages (from-to) | 1013-1036 |

Number of pages | 24 |

Journal | SIAM Journal on Computing |

Volume | 18 |

Issue number | 5 |

DOIs | |

State | Published - 1989 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- General Mathematics