Expected number of iterations of interior-point algorithms for linear programming

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.