FASTER SCALING ALGORITHMS FOR NETWORK PROBLEMS
FASTER SCALING ALGORITHMS FOR NETWORK PROBLEMS
复制标题
DOI：
10.1137/0218069
复制
发表时间：
1989-10-01
影响因子：
1.6
通讯作者：
TARJAN, RE
中科院分区：
文献类型：
--
作者：
GABOW, HN;TARJAN, RE
本文提出了运筹学中的分配问题、运输问题和最小成本流问题的算法。该算法找到一个最小代价的解决方案，但在时间上运行接近最知名的边界对应的问题，没有成本。例如，赋值问题（相当于二部图中的最小代价匹配）可以在time中求解，其中，和n表示代价的顶点数、边数和最大大小；成本被假定为积分。算法通过缩放来工作。正如Goldberg和Tarjan的工作，在每个缩放问题中都找到了一个近似的最优解，而不是一个精确的最优解。
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 intime, where, andNdenote 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.