Polynomial-time highest-gain augmenting path algorithms for the generalized circulation problem

• 成果类型: Article
• 署名作者: Goldfarb, D; Jin, ZY; Orlin, JB
• 署名单位: Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.22.4.793
• 发表日期: 1997
• 页码: 793-802
• 关键词: flow problem

摘要

This paper presents two new combinatorial algorithms for the generalized circulation problem. After an initial step in which all flow-generating cycles are canceled and excesses are created, both algorithms bring these excesses to the sink via highest-gain augmenting paths. Scaling is applied to the fixed amount of flow that the algorithms attempt to send to the sink, and both node and are excesses are used. The algorithms have worst-case complexities of O(m(2)(m + n log n) log B), where n is the number of nodes, m is the number of arcs, and B is the largest integer used to represent the gain factors and capacities in the network. This bound is better than the previous best bound for a combinatorial algorithm for the generalized circulation problem, and if m = O(n(4/3-t)), it is better than the previous best bound for any algorithm for this problem.