Improved Complexity Results on Solving Real-Number Linear Feasibility Problems
Stanford University Stanford, CA We present complexity results on solving real-number standard linear
programs c 0
Uare real. In particular,
we present a two-layered interior-point method and show that ^{n} LP(A,
b, 0), i.e., the linear feasibility problem Ax = b
and x $0, can be solved in in O(n^{2.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 [1]. 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 [1]. We also prove that the
iteration bound will be further reduced to O(n^{1.5} c(A))
for LP(A, 0, 0), i.e., for the homogeneous linear
feasibility problem. [1] S.A. Vavasis and Y. Ye, A Primal-Dual Interior Point Method Whose
Running Time Depends Only on the Constraint Matrix, |