Volume 23, Issue 1
Expected Number of Iterations of Interior-Point Algorithms for Linear Programming

J. Comp. Math., 23 (2005), pp. 93-100.

Published online: 2005-02

Preview Full PDF 532 2480
Export citation

Cited by

• Abstract

We study the behavior of some polynomial interior-point algorithms for solving random linear programming (LP) problems. We show that the expected and anticipated number of iterations of these algorithms is bounded above by $O(n^{1.5})$. The random LP problem is Todd's probabilistic model with the Cauchy distribution.

• Keywords

Linear programming, Interior point algorithms, Probabilistic LP models, Expected number of iterations.

• BibTex
• RIS
• TXT
@Article{JCM-23-93, author = {}, title = {Expected Number of Iterations of Interior-Point Algorithms for Linear Programming}, journal = {Journal of Computational Mathematics}, year = {2005}, volume = {23}, number = {1}, pages = {93--100}, abstract = {

We study the behavior of some polynomial interior-point algorithms for solving random linear programming (LP) problems. We show that the expected and anticipated number of iterations of these algorithms is bounded above by $O(n^{1.5})$. The random LP problem is Todd's probabilistic model with the Cauchy distribution.

}, issn = {1991-7139}, doi = {https://doi.org/}, url = {http://global-sci.org/intro/article_detail/jcm/8799.html} }
TY - JOUR T1 - Expected Number of Iterations of Interior-Point Algorithms for Linear Programming JO - Journal of Computational Mathematics VL - 1 SP - 93 EP - 100 PY - 2005 DA - 2005/02 SN - 23 DO - http://doi.org/ UR - https://global-sci.org/intro/article_detail/jcm/8799.html KW - Linear programming, Interior point algorithms, Probabilistic LP models, Expected number of iterations. AB -

We study the behavior of some polynomial interior-point algorithms for solving random linear programming (LP) problems. We show that the expected and anticipated number of iterations of these algorithms is bounded above by $O(n^{1.5})$. The random LP problem is Todd's probabilistic model with the Cauchy distribution.

Si-Ming Huang. (1970). Expected Number of Iterations of Interior-Point Algorithms for Linear Programming. Journal of Computational Mathematics. 23 (1). 93-100. doi:
Copy to clipboard
The citation has been copied to your clipboard