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

DOI10.1016/J.DAM.2016.06.026MaRDI QIDQ317432zbMATH OpenOpenAlexFDO

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

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

maximum flow problemMBU algorithmpivot algorithm

Mathematics Subject Classification ID

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

Recommendations

• Strongly polynomial dual simplex methods for the maximum flow problem
• On strongly polynomial dual simplex algorithms for the maximum flow problem
• A strongly polynomial algorithm for generalized flow maximization
• A strongly polynomial algorithm for generalized flow maximization
• On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem
• A simpler and faster strongly polynomial algorithm for generalized flow maximization
• A simpler and faster strongly polynomial algorithm for generalized flow maximization
• On strongly polynomial variants of the MBU-simplex algorithm for a maximum flow problem with non-zero lower bounds
• Strongly polynomial Pivot algorithms for maximal flow problems
• Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives

Cites work

• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• scientific article; zbMATH DE number 3349645 (Why is no real title available?)
• A Monotonic Build-Up Simplex Algorithm for Linear Programming
• A polynomial time primal network simplex algorithm for minimum cost flows
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
• Anstreicher–Terlaky type monotonic simplex algorithms for linear feasibility problems
• Exterior point simplex-type algorithms for linear and network optimization problems
• Network flows. Theory, algorithms, and applications.
• On strongly polynomial variants of the MBU-simplex algorithm for a maximum flow problem with non-zero lower bounds
• 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
• 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

Cited in

(4)

• Complexity analysis for maximum flow problems with arc reversals
• Strongly polynomial Pivot algorithms for maximal flow problems
• On strongly polynomial variants of the MBU-simplex algorithm for a maximum flow problem with non-zero lower bounds
• Flow maximization problem as linear programming problem with capacity constraints

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q317432)