Average number of iterations of some polynomial interior-point -- algorithms for linear programming

DOI10.1007/BF02884182zbMath0976.90071OpenAlexW2233483240MaRDI QIDQ1589768

Siming Huang

Publication date: 1 April 2001

Published in: Science in China. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02884182

zbMATH Keywords

random linear programmingaverage number of iterationspolynomial interior-point algorithms

Mathematics Subject Classification ID

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

Related Items (1)

On the probabilistic complexity of finding an approximate solution for linear programming

Cites Work

• A new polynomial-time algorithm for linear programming
• The simplex method. A probabilistic analysis
• A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
• An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
• Probabilistic Analysis of an Infeasible-Interior-Point Algorithm for Linear Programming
• On the average number of steps of the simplex method of linear programming
• A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
• Probabilistic Models for Linear Programming
• Toward Probabilistic Analysis of Interior-Point Algorithms for Linear Programming
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
• Unnamed Item
• Unnamed Item

This page was built for publication: Average number of iterations of some polynomial interior-point -- algorithms for linear programming