PROBABILISTIC ANALYSIS OF TWO COMPLEXITY MEASURES FOR LINEAR PROGRAMMING PROBLEMS

M.J. TODD LEVENT TUNÇEL AND YINYU YE

Abstract. This note provides a probabilistic analysis of χ̄_{A}, a condition number used in the linear programming algorithm of Vavasis and Ye whose running time depends only on the constraint matrix A ∈ ℝ^{m×n}. We show that if A is a standard Gaussian matrix, then E(ln χ̄_{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 σ(A)), where σ(A) is another condition number of A arising in complexity analyses of linear programming problems.