Past Awards
"The 1984 Lanchester Prize is awarded to Dr. Narendra Karmarkar for his paper "A New Polynomial-Time Algorithm For Linear Programming," which appeared in Combinatorica 4 (1984), 373-395. The Committee would also like to mention the preliminary announcement with the same title which appeared in the Proceedings of the 16th Annual ACM Symposium on the Theory of Computing, 1984, 302-311, which contains some expository discussion of the results obtained.
"There have in the last six years been several significant advances in the theory of linear programming. Khachian showed in 1979 that the ellipsoid algorithm of Yudin and Nemirovsky (and related to earlier work of Shor) provided a polynomially bounded algorithm for linear programming. These authors received the 1982 Fulkerson Prize for their contributions. A number of researchers have obtained bounds on the expected number of iterations of certain parametric versions of the simplex method, using a variety of probabilistic models; Borgwardt was the first to obtain a polynomial bound for a complete simplex algorithm, and he received the 1982 Lanchester Prize for his work.
"Recently, another major advance has been made by the development of a new polynomial algorithm by Karmarkar. Similar to the ellipsoid method, this new algorithm ignores basic solutions and uses nonlinear techniques to solve the linear programming problem. Given an initial strictly feasible solution, it generates a sequence of such points with objective function values converging linearly to the optimal value. This suffices to provide a polynomial algorithm for the general linear programming problem. The method combines highly novel techniques with some familiar concepts from nonlinear programming: each iteration performs a projective transformation to approximately center the current point in the feasible region, and then takes a step in the projected gradient direction for the transformed problem. Linear convergence of the objective function values is attained by assuring sufficient decrease in an ingenious auxiliary function, Karmarkar's potential function, which bears some similarity to the classical logarithmic barrier function.
"The ellipsoid method has proved very inefficient in practice for solving linear programming problems; in part, this poor behavior is due to the fact that the method usually takes a number of steps comparable to its worst case bound. On the other hand, preliminary computational experience with variants of Karmarkar's algorithm has demonstrated that it performs far better in practice than its theoretical bound, although the time required depends heavily on the method used to compute the projected gradient. At present, a very conservative claim is that the method holds considerable promise as a viable alternative to the simplex method at least for certain classes of large structured sparse linear programming problems.
"Whatever the eventual verdict on its computational comparison with simplex methods, Karmarkar's paper is an outstanding contribution to the theoretical complexity of linear programming, and the committee is very pleased to acknowledge this significant advance."