A modified layered-step interior-point algorithm for linear programming

DOI10.1007/BF01580074MaRDI QIDQ1290624zbMATH OpenFDO

Authors Nimrod Megiddo, Shinji Mizuno, Takashi Tsuchiya

Publication date 3 June 1999

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

zbMATH Keywords

path of centerscrossover eventslayered-step interior-point algorithm

Mathematics Subject Classification ID

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

Recommendations

• A Variant of the Vavasis--Ye Layered-Step Interior-Point Algorithm for Linear Programming
• An accelerated interior point method whose running time depends only on \(A\) (extended abstract)
• A Low Complexity Interior-Point Algorithm for Linear Programming
• A primal-dual interior point method whose running time depends only on the constraint matrix

Cites work

• scientific article; zbMATH DE number 4202017 (Why is no real title available?)
• scientific article; zbMATH DE number 1489800 (Why is no real title available?)
• A Dantzig-Wolfe-Like Variant of Karmarkar's Interior-Point Linear Programming Algorithm
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A linear programming instance with many crossover events
• A new polynomial-time algorithm for linear programming
• A polynomial-time algorithm for a class of linear complementarity problems
• A primal-dual interior point method whose running time depends only on the constraint matrix
• Global Convergence Property of the Affine Scaling Methods for Primal Degenerate Linear Programming Problems
• Interior path following primal-dual algorithms. I: Linear programming
• Methods for Modifying Matrix Factorizations
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• On scaled projections and pseudoinverses
• Triangular factors of modified matrices

Cited in

(8)

• scientific article; zbMATH DE number 1873243 (Why is no real title available?)
• What Tropical Geometry Tells Us about the Complexity of Linear Programming
• A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms
• A Variant of the Vavasis--Ye Layered-Step Interior-Point Algorithm for Linear Programming
• Log-Barrier Interior Point Methods Are Not Strongly Polynomial
• Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem
• A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
• Improved complexity results on solving real-number linear feasibility problems

This page was built for publication: A modified layered-step interior-point algorithm for linear programming

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