In this paper, we propose a simple variant of the Mizuno-Todd-Ye predictor-corrector algorithm for linear programming. Our variant employs a simple and a natural scaling-invariant search direction aiming at finite-termination, and, even if finite-termination fails, the same direction is occasionally used instead of the ordinary predictor step. Our algorithm is scaling-invariant, is easy to implement, and enjoys an objective-function-free polynomial-time complexity for a linear program with bounded feasible region.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science