Narendra Karmarkar

from Wikipedia, the free encyclopedia

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

Education and career

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

Today Karmarkar is a professor at the Tata Institute of Fundamental Research in Mumbai.


In 1984, Karmarkar published his algorithm while working at Bell Laboratories in New Jersey . The importance of this interior point method was that it was the first solution method for solving linear programs that had both polynomial running time and was practically applicable. It thus stood out from the ellipsoid method published by Leonid Chatschijan in 1979 , which, although polynomial, was not suitable for practical purposes. Karmarkar's algorithm promoted the development of further interior point methods such as Mehrotra's Predictor-Corrector method , some of which are now competitive with the simplex method for solving certain linear programs .

Awards and honors

Web links

Individual evidence

  1. ^ Frederick W. Lanchester Prize. (No longer available online.) ( Institute for Operations Research and the Management Sciences ), archived from the original on October 2, 2015 ; accessed on February 16, 2016 . Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2Template: Webachiv / IABot /