Karmarkar's algorithm and its place in applied mathematics (Q1091259)

Karmarkar's algorithm solves linear programming problems by moving toward the optimal corner from inside the feasible set. The number of steps grows polynomially with the size of the problem, if a projective transformation is applied to change coordinates at each step. In practice a simple rescaling is used, and in many (but not all) problems the algorithm is faster than the simplex method. This paper is an exposition of the main ideas. The key step is a projection onto the nullspace of a matrix (which changes as the algorithm proceeds). This leads to the ''fundamental equation of equilibrium'', whose applications the author develops in his text ''Introduction to applied mathematics'' [Wellesley-Cambridge Press (1986)]. In this paper the examples of resistive networks and of ordering football teams illustrate the fundamental equation (the weighted normal equation) \(AD^ 2A^ Ty=AD^ 2c\). It is on the fast solution of this equation that the success of Karmarkar's algorithm will depend.