Probabilistic Analysis of an Infeasible-Interior-Point Algorithm for Linear Programming

DOI10.1287/moor.24.1.176zbMath0977.90019OpenAlexW2086040751MaRDI QIDQ2757589

Yinyu Ye, Jun Ji, Florian A. Potra, Kurt M. Anstreicher

Publication date: 26 November 2001

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/e7f3961cd393f041bb6a69355c7e6a891d35fdc6

zbMATH Keywords

linear programminginfeasible-interior-point algorithmaverage-case behavior

Mathematics Subject Classification ID

Linear programming (90C05) Interior-point methods (90C51)

Related Items

Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure., Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs, Smoothed analysis of condition numbers and complexity implications for linear programming, Probabilistic analysis of a differential equation for linear programming, On the probabilistic complexity of finding an approximate solution for linear programming, New complexity analysis of the primal-dual method for semidefinite optimization based on the Nesterov-Todd direction, A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points, Conditioning of random conic systems under a general family of input distributions, Average number of iterations of some polynomial interior-point -- algorithms for linear programming