Karmarkar’s algorithm with improved steps

The paper defines a function of the interior of the feasible region of Karmarkar’s canonical linear program with the property that its supremum is bounded above by one, if and only if the optimal value of the linear program is zero. It uses this function to obtain data-dependent steps for Karmarkar’s algorithm. The corresponding reduction in the potential function improves upon the data-independent reduction derived by Padberg. The paper analyzes the general step and considers its potential practical advantages.