Faster Scaling Algorithms for Network Problems
Report ID: TR-111-87Author: Tarjan, Robert E. / Gabow, Harold N.
Date: 1987-08-00
Pages: 33
Download Formats: |PDF|
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, but run in time close to the best-known bounds for the corresponding problems without costs. For example, the assignment problem (equivalently, minimum cost matching on a bipartite graph) can be solved in O(sqrtnm 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. As in the work of Goldberg and Tarjan, in each scaled problem an approximate optimum solution is found, rather than an exact optimum.