## 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.

Contact: ltuncel@math.uwaterloo.ca