EFFICIENCY OF THE PRIMAL NETWORK SIMPLEX ALGORITHM FOR THE MINIMUM-COST CIRCULATION PROBLEM

• 成果类型: Article
• 署名作者: TARJAN, RE
• 署名单位: Nokia Corporation; Nokia Bell Labs; AT&T
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.16.2.272
• 发表日期: 1991
• 页码: 272-291
• 关键词: trees

摘要

We study the number of pivots required by the primal network simplex algorithm to solve the minimum-cost circulation problem. We propose a pivot selection rule with a bound of n(log n)/2 + O(1) on the number of pivots, for an n-vertex network. This is the first known subexponential bound. The network simplex algorithm with this rule can be implemented to run in n(log n)/2 + O(1) time. In the special case of planar graphs, we obtain a polynomial bound on the number of pivots and the running time. We also consider the relaxation of the network simplex algorithm in which cost-increasing pivots are allowed as well as cost-decreasing ones. For this algorithm we propose a pivot selection rule with a bound of O(nm . min{log(nC), m log n}) on the number of pivots, for a network with n vertices, m arcs, and integer arc costs bounded in magnitude by C. The total running time is O(nm log n . min{(log nC), m log n}). This bound is within a logarithmic factor of those of the best previously known algorithms for the minimum-cost circulation problem.