Mj. Todd et al., Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems, MATH PROGR, 90(1), 2001, pp. 59-69
This note studies <(<chi>)over bar>(A), a condition number used in the line
ar programming algorithm of Vavasis and Ye [14] whose running time depends
only on the constraint matrix A is an element of R-mxn, and <(<sigma>)under
bar>(A), a variant of another condition number due to Ye [17] that also ar
ises in complexity analyses of linear programming problems. We provide a ne
w characterization of <(<chi>)over bar>(A) and relate <(<chi>)over bar>(A)
and <(<sigma>)under bar>(A). Furthermore, we show that if A is a standard G
aussian matrix, then E(ln <(<chi>)over bar>(A)) = O(min{m ln n, n}). Thus,
the expected running time of the Vavasis-Ye algorithm for linear programmin
g problems is bounded by a polynomial in m and n for any right-hand side an
d objective coefficient vectors when A is randomly generated in this way. A
s a corollary of the close relation between <(<chi>)over bar>(A) and <(<sig
ma>)under bar>(A), we show that the same bound holds for E(ln<(<sigma>)unde
r bar>(A)).