Narendra Karmarkar

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

Narendra Krishna Karmarkar
Born (1955-11-15) 15 November 1955
Gwalior, Madhya Pradesh, India
Alma materIIT Bombay (B.Tech)
Caltech (M.S.)
University of California, Berkeley (Ph.D.)
Known forKarmarkar's algorithm
Scientific career
FieldsMathematics, Computing Science
InstitutionsBell Labs
ThesisCoping with NP-Hard Problems (1983)
Doctoral advisorRichard M. Karp[1]

He invented one of the first provably polynomial time algorithms for linear programming, which is generally referred to as an 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.

Biography

Karmarkar received his B.Tech in Electrical Engineering from IIT Bombay in 1978, M.S. from the California Institute of Technology in 1979,[3] and Ph.D. in Computer Science from the University of California, Berkeley in 1983 under the supervision of Richard M. Karp.[4] Karmarkar was a post-doctoral research fellow at IBM research(1983), Member of Technical Staff and fellow at Mathematical Sciences Research Center, AT&T Bell Laboratories(1983-1998), professor of mathematics at M.I.T.(1991), at Institute for Advanced study, Princeton(1996), and Homi Bhabha Chair Professor at the Tata Institute of Fundamental Research in Mumbai from 1998 to 2005. He was the scientific advisor to the chairman of the TATA group(2006-2007). During this time, he was funded by Ratan Tata to scale-up the supercomputer he had designed and prototyped at TIFR. The scaled up model ranked ahead of supercomputer in Japan at that time and achieved the best ranking India ever achieved in supercomputing. He was the founding director of Computational Research labs in Pune where the scaling up work was performed. He continues to work on his new architecture for supercomputing.

Work

Karmarkar's algorithm
Main article: Karmarkar's algorithm

Karmarkar's algorithm solves linear programming problems in polynomial time. These problems are represented by a number of linear constraints involving a number of variables. The previous method of solving these problems consisted of considering the problem as a high dimensional solid with 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 implementations of linear program solvers.

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][8]

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).[9] This approach allows him to extend this work to the physical design of machines. He is now publishing updates on his recent work,[10] including an extended abstract.[11] This new paradigm was presented at IVNC, Poland on 16 July 2008,[12] and at MIT on 25 July 2008.[13] Some of his recent work is published at ieeexplore.[14] He delivered a lecture on his on going work at IIT Bombay in September 2013.[15] He gave a four-part series of lectures at FOCM 2014 (Foundations of Computational Mathematics)[16] titled "Towards a Broader View of Theory of Computing". First part of this lecture series is available at Cornell archive.[17]


Awards
  • 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 for "specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing".
  • Srinivasa Ramanujan Birth Centenary Award for 1999, presented by the Prime Minister of India.
  • Distinguished Alumnus Award, Indian Institute of Technology, Bombay, 1996
  • Distinguished Alumnus Award, Computer Science and Engineering, University of California, Berkeley (1993)
  • Fulkerson Prize in Discrete Mathematics given jointly by the American Mathematical Society & Mathematical Programming Society (1988)
  • Fellow of Bell Laboratories (1987– )
  • Texas Instruments Founders' Prize (1986)
  • Marconi International Young Scientist Award (1985)
  • Golden Plate Award of the American Academy of Achievement, presented by former U.S. president (1985)[18][19]
  • Frederick W. Lanchester Prize of the Operations Research Society of America for the Best Published Contributions to Operations Research (1984)
  • President of India gold medal, I.I.T. Bombay (1978)

References
  1. Narendra Karmarkar at the Mathematics Genealogy Project.
  2. Thomson ISI. "Karmarkar, Narendra K., ISI Highly Cited Researchers". Archived from the original on 23 March 2006. Retrieved 20 June 2009.
  3. "Eighty-Fifth Annual Commencement" (PDF). California Institute of Technology. 8 June 1979. p. 13.
  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. Karmarkar, N. K., Ramakrishnan, K.G. Computational results of an interior point algorithm for large scale linear programming., Mathematical Programming. 52: 555-586 (1991)
  7. 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).
  8. 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)
  9. Angier, Natalie (3 December 1984). "Folding the Perfect Corner". Time Magazine. Retrieved 12 July 2008.
  10. Karmarmar, Narendra (11 July 2008). "Narendra Karmarkar's recent research". punetech.com. Retrieved 12 July 2008.
  11. Karmarmar, Narendra (11 July 2008). "Massively Parallel Systems and Global Optimization" (PDF). punetech.com Narendra Karmarkar's recent work. Retrieved 12 July 2008.
  12. Karmarmar, Narendra (14 July 2008). "Vacuum nanoelectronics devices from the perspective of optimization theory" (PDF). punetech.com Narendra Karmarkar's recent work. Retrieved 14 July 2008.
  13. Karmarkar, Narendra. "Seminar on Massively Parallel Systems and Global Optimization". Computation Research in Boston. Retrieved 12 July 2008.
  14. http://ieeexplore.ieee.org/xpl/tocresult.jsp?isnumber=5166089&isYear=2009
  15. Karmarkar, Narendra. "Advanced Algorithmic Approach to Optimization". Research in India. Retrieved 26 September 2003.
  16. https://www.fing.edu.uy/eventos/focm2014/
  17. Karmarkar, Narendra (2014). "Towards a Broader View of Theory of Computing". arXiv:1412.3335 [cs.NA].
  18. "Golden Plate Awardees of the American Academy of Achievement". www.achievement.org. American Academy of Achievement.
  19. "Whiz kids rub elbows with right stuff" (PDF). Rocky Mountain News. 30 June 1985.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.