Polynomial-time primal simplex algorithms for the minimum cost network flow problem

DOI10.1007/BF01758840zbMath0761.90037OpenAlexW2000247330MaRDI QIDQ1193519

Jianxiu Hao, Donald Goldfarb

Publication date: 27 September 1992

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01758840

zbMATH Keywords

minimum cost network flow problempolytope diameterprimal network simplex algorithmcost- scalingminimum mean augmenting cycle-cancelling method

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Deterministic network models in operations research (90B10) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

A polynomial time primal network simplex algorithm for minimum cost flows ⋮ Minimum-cost flow algorithms: an experimental evaluation ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ Convexification of generalized network flow problem

Cites Work

• Unnamed Item
• Unnamed Item
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
• A strongly polynomial minimum cost circulation algorithm
• Parametric shortest path algorithms with an application to cyclic staffing
• Use of dynamic trees in a network simplex algorithm for the maximum flow problem
• A characterization of the minimum cycle mean in a digraph
• On the average number of steps of the simplex method of linear programming
• A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees
• Finding Minimum-Cost Circulations by Successive Approximation
• Finding minimum-cost circulations by canceling negative cycles
• Technical Note—A Polynomial Simplex Method for the Assignment Problem
• Efficient dual simplex algorithms for the assignment problem
• Signature Methods for the Assignment Problem
• On the simplex algorithm for networks and generalized networks
• An efficient implementation of the network simplex method
• Shortest Path and Network Flow Algorithms
• A dual simplex algorithm for finding all shortest paths
• The Average number of pivot steps required by the Simplex-Method is polynomial
• Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem
• Theoretical Properties of the Network Simplex Method
• Efficient Shortest Path Simplex Algorithms
• A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems