A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time

DOI10.1007/BF01580869zbMath0713.90028OpenAlexW2029479369MaRDI QIDQ750277

Jianxiu Hao, Donald Goldfarb

Publication date: 1990

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

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

zbMATH Keywords

primal simplex algorithmstrongly polynomial

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (22)

Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems ⋮ Equivalence of the primal and dual simplex algorithms for the maximum flow problem ⋮ A polynomial time primal network simplex algorithm for minimum cost flows ⋮ On strongly polynomial dual simplex algorithms for the maximum flow problem ⋮ Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm ⋮ Strongly polynomial dual simplex methods for the maximum flow problem ⋮ An augmenting‐flow algorithm for a class of node‐capacitated maximum flow problems ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ Use of dynamic trees in a network simplex algorithm for the maximum flow problem ⋮ On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem ⋮ Maximum flow problem in wireless ad hoc networks with directional antennas ⋮ Exterior point simplex-type algorithms for linear and network optimization problems ⋮ Polynomial-time primal simplex algorithms for the minimum cost network flow problem ⋮ A new?old algorithm for minimum-cut and maximum-flow in closure graphs ⋮ On strongly polynomial variants of the MBU-simplex algorithm for a maximum flow problem with non-zero lower bounds ⋮ A polynomial-time simplex method for the maximum \(k\)-flow problem ⋮ Polynomial dual network simplex algorithms ⋮ A strongly polynomial simplex method for the linear fractional assignment problem ⋮ Computational investigations of maximum flow algorithms ⋮ On the maximum capacity augmentation algorithm for the maximum flow problem ⋮ A comprehensive simplex-like algorithm for network optimization and perturbation analysis ⋮ The maximum flow problem: A max-preflow approach

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Use of dynamic trees in a network simplex algorithm for the maximum flow problem
• A data structure for dynamic trees
• A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem
• Finding minimum-cost circulations by canceling negative cycles
• Improved Time Bounds for the Maximum Flow Problem
• A practicable steepest-edge simplex algorithm
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A network simplex method
• A bad network problem for the simplex method and other minimum cost flow algorithms

This page was built for publication: A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time