Karmarkar Algorithm       


Mathematics Accomplishment | 1983

IBM researcher: Narendra Karmarkar

Where the work was done: IBM San Jose Research Lab

What we accomplished: Karmarkar’s algorithm is an interior-point algorithm for solving linear programming (LP) problems in polynomial time. It was the first polynomial-time algorithm for LP that was claimed to be very practical (whereas the previously-known ellipsoid method was not practical at all).  The algorithm had a huge impact on the field of optimization and inspired the study of interior-point methods beyond LP. It resulted in multiple awards as noted below and the paper has been cited more than 5000 times.

In 1982/83 Dr. Narendra Karmarkar was employed as a postdoc at the IBM San Jose Research Laboratory. During that year he invented what became known as Karmarkar’s Algorithm, which is an interior-point method based on projective transformations of polytopes.  Karmarkar presented his algorithm in a seminar at Stanford University in August 1983, with the announcement noting his affiliation with IBM – San Jose:

August 11, 1983 Stanford Talk
Dr. Narendra Karmarkar, IBM - San Jose
“A new polynomial time algorithm for linear programming based on projective transformations of polytopes.”

Abstract:  “Given a polytope  P  and an interior point  a , we construct a projective transformation that transforms  (P,a)  into  (P’,a’)  with the following property:  B(a’,r)  included in  P’  included in  B(a’,R)  and  R/r=n, where  B(a,r)  denotes the sphere of radius  r  and center  a.  We design a new algorithm for linear programming based on repeated application of such projective transformations.  Worst case running time of this algorithm is better than that of the ellipsoid algorithm by a factor of about  O(n2.5).”

Karmarkar submitted a paper on this algorithm to the 1984 ACM Symposium on Theory of Computing (STOC) while he was an AT&T Bell Labs employee in the fall of 1983.  As will be clear to experts, the abstract of the Stanford talk above and the abstract of the STOC paper below are essentially the same, with the Stanford abstract claiming an improvement of a power of 2.5,  whereas the STOC abstract says that the improvement was a reduction of the power from 6 to 3.5:

Abstract - STOC Paper
“We present a new polynomial-time algorithm for linear programming. The running-time of this algorithm is  O(n3.5L2), as compared to  O(n6L2)  for the ellipsoid algorithm. We prove that given a polytope  P  and a strictly interior point  a ∈ P, there is a projective transformation of the space that maps  P, a  to  P', a'  having the following property. The ratio of the radius of the smallest sphere with center  a', containing  P'  to the radius of the largest sphere with center  a'  contained in  P'  is  O(n). The algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in polynomial-time."

Related link: N. Karmarakar, A new polynomial-time algorithm for linear programming in: Proceedings of the 16th Annual ACM Symposium on Theory of Computing (1984) pp. 302-311.

This work was widely highlighted in the popular press, including The New York Times. Karmarkar has also received major awards for it:

Image credit: IIT Bombay

BACK TO MATHEMATICS
BACK TO IBM RESEARCH ACCOMPLISHMENTS