Strict monotonicity in Todd's low-complexity algorithm for linear programming

DOI10.1016/0167-6377(92)90023-VMaRDI QIDQ1200765zbMATH OpenFDO

Authors Shinji Mizuno, Atsushi Nagasawa

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)90023-V

zbMATH Keywords

interior point algorithmpotential functionstrictly monotone algorithm

Mathematics Subject Classification ID

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

Recommendations

• Strict monotonicity and improved complexity in the standard form projective algorithm for linear programming
• On monotonicity in the scaled potential algorithm for linear programming
• Anstreicher–Terlaky type monotonic simplex algorithms for linear feasibility problems
• A Monotonic Build-Up Simplex Algorithm for Linear Programming
• Solving strongly monotone linear complementarity problems
• Linear k-monotonicity preserving algorithms and their approximation properties
• Monotone variable-metric algorithm for linearly constrained nonlinear programming
• Monotonicity of Mangasarian's iterative algorithm for generalized linear complementarity problems
• Linear time algorithms for convex and monotone approximation
• Improved deterministic algorithms for linear programming in low dimensions

Cites work

• A new polynomial-time algorithm for linear programming
• A variation on Karmarkar’s algorithm for solving linear programming problems
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• scientific article; zbMATH DE number 554743 (Why is no real title available?)
• scientific article; zbMATH DE number 3301975 (Why is no real title available?)
• On monotonicity in the scaled potential algorithm for linear programming
• Todd's low-complexity algorithm is a predictor-corrector path-following method

Cited in

(5)

• Strict monotonicity and improved complexity in the standard form projective algorithm for linear programming
• Reducing a monotone horizontal LCP to an LCP
• Monotonizing linear programs with up to two nonzeroes per column
• Some variants of the Todd low-complexity algorithm
• A simple variant of the Mizuno-Todd-Ye predictor-corrector algorithm and its objective-function-free complexity

This page was built for publication: Strict monotonicity in Todd's low-complexity algorithm for linear programming

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