Narendra Karmarkar

Narendra Krishna Karmarkar, born in 1956, is an Indian mathematician best known for inventing one of the first provably polynomial-time algorithms for linear programming, the method now called Karmarkar's algorithm, a cornerstone of the interior point family of methods. He studied electrical engineering at IIT Bombay, took a master's degree at the California Institute of Technology, and completed a doctorate in computer science at the University of California, Berkeley in 1983 under Richard M. Karp. He published the algorithm in 1984 while at Bell Laboratories in New Jersey. Instead of walking from vertex to vertex of the feasible solid as earlier methods did, his approach cuts through its interior, which made large optimization problems such as communications network planning far quicker to solve and stimulated many later interior-point solvers. He later held posts at MIT, the Institute for Advanced Study and the Tata Institute of Fundamental Research, and turned to supercomputer architecture based on finite and projective geometry. His honours include the Paris Kanellakis Award, the Fulkerson Prize and the Lanchester Prize.