On the number of iterations of Karmarkar’s algorithm for linear programming

Karmarkar’s algorithm for linear programming was published in 1984, and it is highly important to both theory and practice. On the practical side some of its variants have been found to be far more efficient than the simplex method on a wide range of very large calculations, while its polynomial time properties are fundamental to research on complexity. These properties depend on the fact that each iteration reduces a ‘potential function’ by an amount that is bounded away from zero, the bound being independent of all the coefficients that occur. It follows that, under mild conditions on the initial vector of variables, the number of iterations that are needed to achieve a prescribed accuracy in the final value of the linear objective function is at most a multiple of n, where n is the number of inequality constraints. By considering a simple example that allows n to be arbitrarily large, the authors deduce analytically that the magnitude of this complexity bound is correct. Specifically, they prove that the solution of the example by Kamarkar’s original algorithm can require about n/20 iterations. Further, the authors find that the algorithm makes changes to the variables that are closely related to the steps of the simplex method.