Recovering optimal basic variables in Karmarkar’s polynomial algorithm for linear programming

Primal-slack ellipsoids are described which contain all of the optimal primal feasible solutions in a standard form variant of Karmarkar’s projective algorithm for linear programming (LP). Using these ellipsoids, the paper shows how to identify optimal basic variables using few additional arithmetic operations and also simultaneously reduce the size of the LP problem during the course of the algorithm. Some preliminary computational experiments are given which compare different stopping criteria.