A new strongly polynomial dual network simplex algorithm

DOI10.1007/BF02614366zbMath0890.90061MaRDI QIDQ1373742

Ronald D. Armstrong, Zhiying Jin

Publication date: 25 November 1997

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

minimum cost network flowdual network simplex algorithm

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10)

Related Items (4)

Exact and parameterized algorithms for read-once refutations in Horn constraint systems ⋮ A polynomial time primal network simplex algorithm for minimum cost flows ⋮ Dynamic network flow location models and algorithms for quickest evacuation planning ⋮ Exterior point simplex-type algorithms for linear and network optimization problems

Cites Work

• Unnamed Item
• Polynomial dual network simplex algorithms
• A strongly polynomial minimum cost circulation algorithm
• Solving linear bottleneck assignment problems via strong spanning trees
• Strongly polynomial simplex algorithm for bipartite vertex packing
• Maximum matchings in bipartite graphs via strong spanning trees
• Efficient dual simplex algorithms for the assignment problem
• A competitive (dual) simplex method for the assignment problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A network simplex method
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm

This page was built for publication: A new strongly polynomial dual network simplex algorithm