Narendra Karmarkar

Narendra Krishna Karmarkar
Born Gwalior
Fields Mathematics, Computing Science
Institutions Bell Labs
Alma mater Indian Institute of Technology Bombay, California Institute of Technology, University of California, Berkeley
Thesis Coping with NP-Hard Problems (1983)
Doctoral advisor Richard M. Karp[1]
Known for Karmarkar's algorithm

Narendra Krishna Karmarkar (born 1957) is an Indian mathematician, who developed Karmarkar's algorithm. He is listed as an ISI highly cited researcher.[2]

Biography

Narendra Karmarkar was born in a Maharashtrian family in Gwalior. After securing an All India Rank 1 in the Joint Entrance Examination conducted by the prestigious IITs (IIT-JEE), he took admission in the Indian Institute of Technology Bombay. Karmarkar received his B.Tech in Electrical Engineering from IIT Bombay in 1978, M.S. from the California Institute of Technology[3] and Ph.D. in Computer Science from the University of California, Berkeley in 1983 under the supervision of Richard M. Karp.[4]

He invented a polynomial algorithm for linear programming also known as the interior point method. The algorithm is a cornerstone in the field of Linear Programming. He published his famous result in 1984 while he was working for Bell Laboratories in New Jersey. Karmarkar was a professor at the Tata Institute of Fundamental Research in Mumbai. He is currently working on a new architecture for supercomputing.

Karmarkar has received a number of awards:

Work

Karmarkar's algorithm

Main article: Karmarkar's algorithm

Karmarkar's algorithm solves linear programming problems in polynomial time. These problems are represented by "n" variables and "m" constraints. The previous method of solving these problems consisted of problem representation by an "x" sided solid with "y" vertices, where the solution was approached by traversing from vertex to vertex. Karmarkar's novel method approaches the solution by cutting through the above solid in its traversal. Consequently, complex optimization problems are solved much faster using the Karmarkar algorithm. A practical example of this efficiency is the solution to a complex problem in communications network optimization where the solution time was reduced from weeks to days. His algorithm thus enables faster business and policy decisions. Karmarkar's algorithm has stimulated the development of several interior point methods, some of which are used in current codes for solving linear programs.

Paris Kanellakis Award

The Association for Computing Machinery awarded him the prestigious Paris Kanellakis Award in 2000 for his work on polynomial time interior point methods for linear programming.

Galois geometry

After working on the Interior Point Method, Karmarkar worked on a new architecture for supercomputing, based on concepts from finite geometry, especially projective geometry over finite fields.[5][6][7]

Current investigations

Currently, he is synthesizing these concepts with some new ideas he calls sculpturing free space (a non-linear analogue of what has popularly been described as folding the perfect corner).[8] This approach allows him to extend this work to the physical design of machines. He is now publishing updates on his recent work,[9] including an extended abstract.[10] This new paradigm was presented at IVNC, Poland on 16 July 2008,[11] and at MIT on 25 July 2008.[12] Some of his recent work is published at ieeexplore.[13] He delivered a lecture on his on going work at IIT Bombay in September 2013.[14] He gave a four part series of lectures at FOCM 2014 (Foundations of Computational Mathematics)[15] titled "Towards a Broader View of Theory of Computing". First part of this lecture series is available at Cornell archive.[16]

References

  1. ↑ Narendra Karmarkar at the Mathematics Genealogy Project.
  2. ↑ Thomson ISI. "Karmarkar, Narendra K., ISI Highly Cited Researchers". Retrieved 2009-06-20.
  3. ↑ http://caltechcampuspubs.library.caltech.edu/2515/1/June_8,_1979.pdf
  4. ↑ Narendra Karmarkar at the Mathematics Genealogy Project
  5. ↑ Karmarkar, Narendra. "A new parallel architecture for sparse matrix computation based on finite projective geometries". Proceedings of the 1991 ACM/IEEE conference on Supercomputing.
  6. ↑ 28. Amruter, B. S., Joshi, R., Karmarkar, N. K., A Projective Geometry Architecture for Scientific Computation, Proceedings of International Conference on Application Specific Array Processors, IEEE Computer Society , pp 6480 (1992).
  7. ↑ Karmarkar, N. K., A New Parallel Architecture for Scientific Computation Based on Finite Projective Geometries, Proceeding of Mathematical Programming, State of the Art, pp. 136148 (1994)
  8. ↑ Angier, Natalie (1984-12-03). "Folding the Perfect Corner". Time Magazine. Retrieved 2008-07-12.
  9. ↑ Karmarmar, Narendra (2008-07-11). "Narendra Karmarkar's recent research". punetech.com. Retrieved 2008-07-12.
  10. ↑ Karmarmar, Narendra (2008-07-11). "Massively Parallel Systems and Global Optimization" (PDF). punetech.com Narendra Karmarkar's recent work. Retrieved 2008-07-12.
  11. ↑ Karmarmar, Narendra (2008-07-14). "Vacuum nanoelectronics devices from the perspective of optimization theory" (PDF). punetech.com Narendra Karmarkar's recent work. Retrieved 2008-07-14.
  12. ↑ Karmarkar, Narendra. "Seminar on Massively Parallel Systems and Global Optimization". Computation Research in Boston. Retrieved 2008-07-12.
  13. ↑ http://ieeexplore.ieee.org/xpl/tocresult.jsp?isnumber=5166089&isYear=2009
  14. ↑ Karmarkar, Narendra. "Advanced Algorithmic Approach to Optimization". Research in India. Retrieved 2003-09-26.
  15. ↑ https://www.fing.edu.uy/eventos/focm2014/
  16. ↑ http://arxiv.org/abs/1412.3335

External links

This article is issued from Wikipedia - version of the Monday, February 08, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.