Narendra Karmarkar

Narendra B. Karmarkar ( born 1957 ) is an Indian mathematician. His most important contribution was the development of a polynomial algorithm for solving linear programs in 1984.

Karmarkar received his bachelor's degree in 1978 from the Indian Institute of Technology in Mumbai. He later obtained a Master of Science at the California Institute of Technology in 1983 and his PhD at the Institute of computer science at the University of California, Berkeley.

In 1984, Karmarkar published his algorithm, when he worked at Bell Laboratories in New Jersey. The importance of interior-point method was that it was the first solution method for solving linear programs, which possessed both polynomial runtime as was practical. Thus, it stood out from the published in 1979 by Leonid Chatschijan ellipsoid method, which was indeed polynomial, but not suitable for practical purposes. Karmarkars algorithm promoted the development of other interior-point methods such as Mehrotra's Predictor - Corrector methods, some of which now are competitive to the simplex method in solving specific linear programs.

For his discovery Karmarkar received numerous awards, including the Fulkerson Prize from the Mathematical Programming Society, the Paris Kanellakis Award of the Association for Computing Machinery, and the Frederick W. Lanchester Prize of the Operations Research Society of America. Today Karmarkar has been a professor at the Tata Institute of Fundamental Research in Mumbai.