Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems

DOI10.1016/j.dam.2016.06.026zbMath1351.90050OpenAlexW2290596303MaRDI QIDQ317432

Richárd Molnár-Szipai, Tibor Illés

Publication date: 30 September 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.cs.elte.hu/opres/orr/download/ORR_2015_02.pdf

zbMATH Keywords

pivot algorithmmaximum flow problemMBU algorithm

Mathematics Subject Classification ID

Linear programming (90C05) Deterministic network models in operations research (90B10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exterior point simplex-type algorithms for linear and network optimization problems
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
• On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem
• Pivot rules for linear programming: A survey on recent theoretical developments
• A polynomial time primal network simplex algorithm for minimum cost flows
• Strongly polynomial dual simplex methods for the maximum flow problem
• The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A Monotonic Build-Up Simplex Algorithm for Linear Programming
• On strongly polynomial variants of the MBU-simplex algorithm for a maximum flow problem with non-zero lower bounds
• Anstreicher–Terlaky type monotonic simplex algorithms for linear feasibility problems

This page was built for publication: Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems