On network simplex method using the primal–dual symmetric pivoting rule

We consider a network simplex method using the primal–dual symmetric pivoting rule proposed by Chen, Pardalos, and Saunders. For minimum-cost network-flow problems, we prove global convergence of the algorithm and propose a new scheme in which the algorithim can start from an arbitrary pair of primal and dual feasible spanning trees. For shortest-path problems, we prove the strongly polynomial time complexity of the algorithm.