On partial updating in a potential reduction linear programming algorithm of Kojima, Mizuno, and Yoshise

DOI10.1007/BF01188712zbMath0764.90052OpenAlexW2050681410MaRDI QIDQ1206441

Kurt M. Anstreicher, Robert A. Bosch

Publication date: 1 April 1993

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

interior-point methodpartial updatingprimal-dual potential reduction approach

Mathematics Subject Classification ID

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

Related Items (3)

Potential-reduction methods in mathematical programming ⋮ An interior point method, based on rank-1 updates, for linear programming ⋮ An \(O(n^ 3 L)\) primal-dual potential reduction algorithm for solving convex quadratic programs

Cites Work

• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• A standard form variant, and safeguarded linesearch, for the modified Karmarkar algorithm
• Computing Karmarkar projections quickly
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Interior path following primal-dual algorithms. I: Linear programming
• Interior path following primal-dual algorithms. II: Convex quadratic programming
• A polynomial-time algorithm for a class of linear complementarity problems
• An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
• Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
• An \(O(n^ 3L)\) adaptive path following algorithm for a linear complementarity problem
• Long steps in an \(O(n^ 3L)\) algorithm for linear programming
• Large Step Path-Following Methods for Linear Programming, Part I: Barrier Function Method
• A Complexity Reduction for the Long-Step Path-Following Algorithm for Linear Programming
• An $O(\sqrt{n} L)$-Iteration Large-Step Primal-Dual Affine Algorithm for Linear Programming
• An Implementation of a Primal-Dual Interior Point Method for Linear Programming

This page was built for publication: On partial updating in a potential reduction linear programming algorithm of Kojima, Mizuno, and Yoshise