Probabilistic analysis of two complexity measures for linear programming problems

M.J. Todd, Levent Tuncel and Yinyu Ye

This note provides a probabilistic analysis of $\bar\chi_A$, a condition number used in the linear programming algorithm of Vavasis and Ye \cite{VavasisYe} whose running time depends only on the constraint matrix $A\in \R^{m\times n}$. We show that if $A$ is a standard Gaussian matrix, then $E(\ln\bar\chi_A) = O(\min\{m\ln n, n\})$. Thus, the expected running time of linear programming is bounded by a polynomial in $m$ and $n$ for any right-hand side and objective coefficient vectors when $A$ is randomly generated in this way. We show that the same bound holds for $E(\ln \sigma(A))$, where $\sigma(A)$ is another condition number of $A$ arising in complexity analyses of linear programming problems.

TR 1219, School of Operations Research and Industrial Engineering, Cornell University, Ithaca NY, USA. Also: CORR 98-48, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada, October 1998.