On Complexity of Linear Programming

ABSTRACT

We present improved results on the real number complexity of linear programming. In particular, we show that the real system Ax = b and x >= 0 can be solved in O(n ^2.5 C (A)) iterations by a new layered interior-point method, and each iteration solves a linear least-squares problem, where n is the dimension of vector x and C(A) is a condition number of real matrix A. This complexity bound is reduced by a factor n from the Vavasis-Ye layered interior-point method.