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

DOI10.1007/BF01580074zbMATH Open0920.90098MaRDI QIDQ1290624FDOQ1290624

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)

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

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)

Cites Work

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

Cited In (8)

• 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
• Title not available (Why is that?)

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)