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

DOI10.1007/BF01580074zbMath0920.90098MaRDI QIDQ1290624

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

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

Related Items

Log-Barrier Interior Point Methods Are Not Strongly Polynomial, 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, What Tropical Geometry Tells Us about the Complexity of Linear Programming, Improved complexity results on solving real-number linear feasibility problems, 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

Cites Work

• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• On scaled projections and pseudoinverses
• Interior path following primal-dual algorithms. I: 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
• A linear programming instance with many crossover events
• Triangular factors of modified matrices
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Global Convergence Property of the Affine Scaling Methods for Primal Degenerate Linear Programming Problems
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• Methods for Modifying Matrix Factorizations
• A Dantzig-Wolfe-Like Variant of Karmarkar's Interior-Point Linear Programming Algorithm