Toward probabilistic analysis of interior-point algorithms for linear programming

The paper proposes an approach based on interior-point algorithms for linear programming (LP). It shows that the algorithm solves a class of LP problems in strongly polynomial time, -iteration, where each iteration solves a system of linear equations with n variables. The recent statistical data of the solutions of the NETLIB LP problems seem to indicate that virtually all of these problems are in this class. Then, the paper shows that some random LP problems, with high probability (probability converges to one as n approaches infinity), are in this class. These random LP problems include recent Todd's probabilistic models with the standard Gauss distribution.