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 - <p style="text-align: justify;">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&#39;s probabilistic model with the Cauchy distribution.</p>