Faster scaling algorithms for network problems

Harold N. Gabow, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

265 Scopus citations

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 languageEnglish (US)
Pages (from-to)1013-1036
Number of pages24
JournalSIAM Journal on Computing
Volume18
Issue number5
DOIs
StatePublished - 1989

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Faster scaling algorithms for network problems'. Together they form a unique fingerprint.

Cite this