A primal-dual affine-scaling potential-reduction algorithm for linear programming

The authors propose a potential-reduction algorithm which always uses the primal-dual affine-scaling direction as a search direction. They choose a step size at each iteration of the algorithm such that the potential function does not increase, so that a longer step size than the minimizing point of the potential function can be taken. The authors show that the algorithm is polynomial-time bounded. They also propose a low-complexity algorithm, in which the centering direction is used whenever an iterate is far from the path of centers.