A Variant of the Vavasis--Ye Layered-Step Interior-Point Algorithm for Linear Programming

DOI10.1137/S1052623401388926zbMath1044.65052OpenAlexW2127378310MaRDI QIDQ4441937

Renato D. C. Monteiro, Takashi Tsuchiya

Publication date: 19 January 2004

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s1052623401388926

zbMATH Keywords

linear programminginterior-point algorithmscondition numberpolynomial complexitycentral pathpath-followingpredictor-correctorprimal-dual algorithmsaffine scalingstrongly polynomiallayered steps

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Interior-point methods (90C51)

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