# Narendra Karmarkar: Wikis

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

# Encyclopedia

Updated live from Wikipedia, last check: May 20, 2013 14:42 UTC (47 seconds ago)

Narendra K. Karmarkar (born 1957) is an Indian mathematician, renowned for developing Karmarkar's algorithm. He is listed as an ISI highly cited researcher.[1]

## Biography

Narendra Karmarkar was born in Nashik to a Marathi family. He studied in Jain Balika Vidyalaya till Class 12. Karmarkar received his B.Tech at the IIT Bombay in 1978. Later, he received his M.S. at the California Institute of Technology, and his Ph.D. at the Institute of Computer Science at the University of California, Berkeley.

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 Bombay.

He is currently working on a new architecture for supercomputing. Some of the ideas are published at [2] and Fab5 conference organised by MIT center for bits and atoms. [3]

In 2006, he started a company, with funding from Mr. Ratan Tata to the tune of INR 400 crore (US\$ 80 Million), in the field of High Performance Computing.[4] However, he has since abandoned the company over differences with the Tata group concerning the basic objectives behind the project.[5]

Karmarkar received a number of awards for his algorithm, among them:

## Work

### 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 other 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. The award citation reads:

For his theoretical work in devising an Interior Point method for linear programming that provably runs in polynomial time, and for his implementation work suggesting that Interior Point methods could be effective for linear programming in practice as well as theory. Together, these contributions inspired a renaissance in the theory and practice of linear programming, leading to orders of magnitude improvement in the effectiveness of widely-used commercial optimization codes.

### Current Work

After working on the Interior Point Method, Karmarkar worked on a new architecture for supercomputing, based on concepts from projective geometry.[6] 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).[7] This approach allows him to extend this work to the physical design of machines. He is now publishing updates on his recent work,[8] including an extended abstract.[9] This new paradigm was presented at IVNC, Poland on 16 July 2008,[10] and at MIT on 25 July 2008.[11] Some of the recent work is published at [12] and Fab5 conference organised by MIT center for bits and atoms

## References

1. ^ Thomson ISI, Karmarkar, Narendra K., ISI Highly Cited Researchers, retrieved 2009-06-20
2. ^ http://ieeexplore.ieee.org/xpl/tocresult.jsp?isnumber=5166089&isYear=2009
3. ^ http://cba.mit.edu/events/09.08.FAB5/
4. ^ The Hindu Business Line : Tatas plan supercomputer venture
5. ^ Why is Karmarkar out of Tata's project?- Hardware-Infotech-The Economic Times
6. ^ Karmarkar, Narendra. "A new parallel architecture for sparse matrix computation based on finite projective geometries". Proceedings of the 1991 ACM/IEEE conference on Supercomputing.
7. ^ Angier, Natalie (1984-12-03). "Folding the Perfect Corner". Time Magazine. Retrieved 2008-07-12.
8. ^ Karmarmar, Narendra (2008-07-11). "Narendra Karmarkar's recent research". punetech.com. Retrieved 2008-07-12.
9. ^ Karmarmar, Narendra (2008-07-11). "Massively Parallel Systems and Global Optimization" (PDF). punetech.com Narendra Karmarkar's recent work. Retrieved 2008-07-12.
10. ^ 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.
11. ^ Karmarkar, Narendra. "Seminar on Massively Parallel Systems and Global Optimization". Computation Research in Boston. Retrieved 2008-07-12.
12. ^ http://ieeexplore.ieee.org/xpl/tocresult.jsp?isnumber=5166089&isYear=2009