Improved Complexity Results on Solving Real-Number Linear Feasibility Problems
We present complexity results on solving real-number standard linear programs LP(A, b, c), where the constraint matrix A 0 Um×n , the right-hand-side vector b 0 Um and the objective coefficient vector c 0 Un are real. In particular, we present a two-layered interior-point method and show that LP(A, b, 0), i.e., the linear feasibility problem Ax = b and x $0, can be solved in in O(n2.5 c(A)) interior-point method iterations. Here z is the vector of all zeros and c(A) is the condition measure of matrix A defined by Vavasis and Ye . This complexity iteration bound is reduced by a factor n from that for general LP(A, b, c) comparing the results of Vavasis and Ye . We also prove that the iteration bound will be further reduced to O(n1.5 c(A)) for LP(A, 0, 0), i.e., for the homogeneous linear feasibility problem.
 S.A. Vavasis and Y. Ye, A Primal-Dual Interior Point Method Whose Running Time Depends Only on the Constraint Matrix, Mathematical Programming, 74, (1996) 79-120.