Todd's low-complexity algorithm is a predictor-corrector path-following method

DOI10.1016/0167-6377(92)90025-XzbMath0768.90055OpenAlexW1975830103MaRDI QIDQ1197903

Michael J. Todd, Jean-Philippe Vial

Publication date: 16 January 1993

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(92)90025-x

zbMATH Keywords

interior-point methodpredictor-corrector path-following

Mathematics Subject Classification ID

Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Superlinear convergence of the affine scaling algorithm, The implementation of linear programming algorithms based on homotopies, Strict monotonicity in Todd's low-complexity algorithm for linear programming

Cites Work

• Unnamed Item
• A new polynomial-time algorithm for linear programming
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• A polynomial method of approximate centers for linear programming
• Strict monotonicity and improved complexity in the standard form projective algorithm for linear programming
• Limiting behavior of the affine scaling continuous trajectories for linear programming problems
• On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
• A variation on Karmarkar’s algorithm for solving linear programming problems
• A Low Complexity Interior-Point Algorithm for Linear Programming
• A Path-Following Projective Interior Point Method for Linear Programming
• Short Steps with Karmarkar’s Projective Algorithm for Linear Programming