TOWARD PROBABILISTIC ANALYSIS OF INTERIOR-POINT ALGORITHMS FOR LINEAR-PROGRAMMING

We propose an approach based on interior-point algorithms for linear p rogramming (LP). We show that the algorithm solves a class of LP probl ems in strongly polynomial time, O(square-root n log n)-iteration, whe re each iteration solves a system of linear equations with n variables . The recent statistical data of the solutions of the NETLIB LP proble ms seem to indicate that virtually all of these problems are in this c lass. Then, we show that some random LP problems, with high probabilit y (probability converges to one as n approaches infinity), are in this class. These random LP problems include recent Todd's probabilistic m odels with the standard Gauss distribution.