Karmarkar’s Linear Programming Algorithm

Abstract

N. Karmarkar’s new projective scaling algorithm for linear programming has caused quite a stir in the press, mainly because of reports that it is 50 times faster than the simplex method on large problems. It also has a polynomial bound on worst-case running time that is better than the ellipsoid algorithm’s. Radically different from the simplex method, it moves through the interior of the polytope, transforming the space at each step to place the current point at the polytope’s center. The algorithm is described in enough detail to enable one to write one’s own computer code and to understand why it has polynomial running time. Some recent attempts to make the algorithm live up to its promise are also reviewed.