The minimum mean cycle-canceling algorithm for linear programs

DOI10.1016/J.EJOR.2021.09.022MaRDI QIDQ2076908zbMATH OpenOpenAlexFDO

Authors Jean Bertrand Gauthier, Jacques Desrosiers

Publication date 22 February 2022

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2021.09.022

zbMATH Keywords

complexity analysiscycle cancellationinterior directionlinear programresidual problem

Mathematics Subject Classification ID

Linear programming (90C05) Extreme-point and pivoting methods (90C49)

Recommendations

• New polynomial-time cycle-canceling algorithms for minimum-cost flows
• Two strongly polynomial cut cancelling algorithms for minimum cost network flow
• About the minimum mean cycle-canceling algorithm
• Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks
• scientific article; zbMATH DE number 1445399

Cites work

• A characterization of the minimum cycle mean in a digraph
• A new polynomial-time algorithm for linear programming
• A strongly polynomial contraction-expansion algorithm for network flow problems
• About the minimum mean cycle-canceling algorithm
• An improved primal simplex algorithm for degenerate linear programs
• Automation and Combination of Linear-Programming Based Stabilization Techniques in Column Generation
• Decomposition theorems for linear programs
• Dynamic Aggregation of Set-Partitioning Constraints in Column Generation
• Finding minimum-cost circulations by canceling negative cycles
• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• Influence of the normalization constraint on the integral simplex using decomposition
• Linear fractional approximations for master problems in column generation
• Linear Programming
• Network flows. Theory, algorithms, and applications.
• Programming with linear fractional functionals
• Steepest-edge simplex algorithms for linear programming
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Tight bounds on the number of minimum-mean cycle cancellations and related results
• Vector Space Decomposition for Solving Large-Scale Linear Programs

Cited in

(7)

• Cycling in linear programming problems
• Decomposition theorems for linear programs
• On circuit diameter bounds via circuit imbalances
• scientific article; zbMATH DE number 1445399 (Why is no real title available?)
• About the minimum mean cycle-canceling algorithm
• Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks
• On circuit diameter bounds via circuit imbalances

This page was built for publication: The minimum mean cycle-canceling algorithm for linear programs

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