An \(O(\sqrt {n} L)\) iteration bound primal-dual cone affine scaling algorithm for linear programming

DOI10.1007/BF02592088zbMath0853.90085OpenAlexW1498125507MaRDI QIDQ1919092

Shu-Zhong Zhang, Jos F. Sturm

Publication date: 17 October 1996

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

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

zbMATH Keywords

primal-dual interior point algorithmprimal-dual central pathpolynomialityprimal-dual affine scaling method

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05)

Related Items

A circular cone relaxation primal interior point algorithm for LP, Polynomial primal-dual cone affine scaling for semidefinite programming, Approximate cone factorizations and lifts of polytopes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Conical projection algorithms for linear programming
• Interior path following primal-dual algorithms. I: Linear programming
• A primal projective interior point method for linear programming
• A unified approach to interior point algorithms for linear complementarity problems: A summary
• Global convergence of the affine scaling methods for degenerate linear programming problems
• A survey of search directions in interior point methods for linear programming
• A primal-dual affine-scaling potential-reduction algorithm for linear programming
• Constant potential primal-dual algorithms: A framework
• The largest step path following algorithm for monotone linear complementarity problems
• An implementation of Karmarkar's algorithm for linear programming
• New complexity results for the Iri-Imai method
• Search directions for interior linear-programming methods
• A Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension
• A new variant of the primal affine scaling algorithm for linear programs
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• Global Convergence of a Long-Step Affine Scaling Algorithm for Degenerate Linear Programming Problems
• A Polynomial Primal-Dual Dikin-Type Algorithm for Linear Programming