Two new infeasible interior-point predictor-corrector algorithms for l
inear programming are proposed; one uses a Newton direction and the ot
her uses a Euler direction for the predictor step. They require the so
lutions of two linear systems at each iteration. The algorithms are gl
obally convergent, and epsilon-feasibility and epsilon-complementarity
can be obtained in O(nln(1/epsilon)) iterations with proper initializ
ation. The first algorithm is also quadratically convergent under the
assumption that an optimal solution exists.