Expected Number of Iterations of Interior-Point Algorithms for Linear Programming

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.