Title: A first-order predictor-corrector algorithm for linear programming in a wide neighborhood of the central path with improved iteration complexity

It is well known that for linear programs the best known iteration complexity of Mizuno-Todd-Ye type one-order predictor-corrector methods, based on wide neighborhoods, is O(nL). An interesting and important question is whether or not this complexity for these one-order methods can be further reduced? In this paper, we give an affirmative answer to the above question. We prove a class of MTY one-order predictor-corrector algorithm, working in a wide neighborhood, has O(n^(3/4) logn log (x0^Ts0/ε) ) iteration complexity and retains super-linear convergence.