TY - JOUR

T1 - Faster scaling algorithms for network problems

AU - Gabow, Harold N.

AU - Tarjan, Robert E.

N1 - Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 1989

Y1 - 1989

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0024748699&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024748699&partnerID=8YFLogxK

U2 - 10.1137/0218069

DO - 10.1137/0218069

M3 - Article

AN - SCOPUS:0024748699

VL - 18

SP - 1013

EP - 1036

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 5

ER -