O(n\({}^ pL)\)-iteration and \(O(n^ 3L)\)-operation potential reduction algorithms for linear programming

DOI10.1016/0024-3795(91)90273-YzbMath0728.65057WikidataQ112879926 ScholiaQ112879926MaRDI QIDQ805163

Shinji Mizuno

Publication date: 1991

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

zbMATH Keywords

linear programmingpolynomial algorithmpotential reduction algorithm\(O(n^ 3L)\)-operation algorithmsKarmarkar-algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05)

Related Items (4)

Potential-reduction methods in mathematical programming ⋮ Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems ⋮ An \(O(n^ 3L)\) adaptive path following algorithm for a linear complementarity problem ⋮ An interior point method, based on rank-1 updates, for linear programming

Cites Work

• A new polynomial-time algorithm for linear programming
• An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Interior path following primal-dual algorithms. I: Linear 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
• A new polynomial time method for a linear complementarity problem
• AN O(n^3L) ALGORITHM USING A SEQUENCE FOR A LINEAR COMPLEMENTARITY PROBLEM
• A Centered Projective Algorithm for Linear Programming

This page was built for publication: O(n\({}^ pL)\)-iteration and \(O(n^ 3L)\)-operation potential reduction algorithms for linear programming