A feasible predictor-corrector Linear Programming variant of Mehrotra’s algorithm, that was shown to have good performance on transportation and assignment problems, was developed by Bastos and Paixão. We prove the theoretical efficiency of this algorithm by showing its polynomial complexity and its superlinear convergence.

CEMAT - Center for Computational and Stochastic Mathematics