In this paper, the authors present a new primal simplex pivot rule and analyze the worst case complexity of the resulting simple algorithm for the minimum cost flow, the assignment, and the shortest path problems. They consider networks with n nodes, m arcs, integral arc capacities bounded by an integer number U, and integral arc costs whose magnitudes are bounded by an integer number C. The present pivot rule may be regarded as a scaling version of Dantzig’s pivot rule. The pivot rule defines a threshold value ℝ, which is initially at most 2C, and the rule permits any arc with a violation of at least ℝ/2 to be the editing variable. The authors select the leaving arc so that strong feasibility of the basis is maintained. When there is no arc satisfying this rule, then they replace ℝ by ℝ/2 and repeat the process. The algorithm terminates when ℝ<1. The authors show that the simplex algorithm using this rule O(nmUlogC) pivots and can be implemented to run in O(m2UlogC) time. Specializing these results for the assignment and shortest path problems they show that the simplex algorithm solves these problems in O(n2logC) pivots and O(nmlogC) time.
