Faster Scaling Algorithms for Network Problems,
Abstract
This paper presents algorithms for the assignment problem, the transportation problem and the minimum cost flow problem of operations research. The algorithms finds 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((sq rt n)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 scales problem an approximate optimum solution is found, rather than an exact optimum.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1987
- Accession Number
- ADA194032
Entities
People
- Harold N. Gabow
- Robert Tarjan
Organizations
- Princeton University