On network simplex method using primal-dual symmetric pivoting rule

Abstract 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 algorithm 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. 1