Narendra Karmarkar

Last updated

Narendra Krishna Karmarkar
Borncirca 1956
Gwalior, Madhya Pradesh, India
Alma mater IIT Bombay (B.Tech)
Caltech (MS)
University of California, Berkeley (PhD)
Known for Karmarkar's algorithm
Scientific career
Fields Mathematics, computing science
Institutions Bell Labs
Thesis Coping with NP-Hard Problems (1983)
Doctoral advisor Richard M. Karp [1]

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

Contents

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, MS from the California Institute of Technology in 1979, [3] and PhD 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

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's 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,[ when? ] 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 IEEE Xplore. [14] He delivered a lecture on his ongoing 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

Related Research Articles

<span class="mw-page-title-main">Linear programming</span> Method to solve some optimization problems

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming.

<span class="mw-page-title-main">Mathematical optimization</span> Study of mathematical algorithms for optimization problems

Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

Magma is a computer algebra system designed to solve problems in algebra, number theory, geometry and combinatorics. It is named after the algebraic structure magma. It runs on Unix-like operating systems, as well as Windows.

<span class="mw-page-title-main">Theoretical computer science</span> Subfield of computer science and mathematics

Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, formal language theory, the lambda calculus and type theory.

Algorithmic topology, or computational topology, is a subfield of topology with an overlap with areas of computer science, in particular, computational geometry and computational complexity theory.

The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.

<span class="mw-page-title-main">Interior-point method</span> Algorithms for solving convex optimization problems

Interior-point methods are a certain class of algorithms that solve linear and nonlinear convex optimization problems.

Karmarkar's algorithm is an algorithm introduced by Narendra Karmarkar in 1984 for solving linear programming problems. It was the first reasonably efficient algorithm that solves these problems in polynomial time. The ellipsoid method is also polynomial time but proved to be inefficient in practice.

In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm which finds an optimal solution in a number of steps that is polynomial in the input size.

<span class="mw-page-title-main">Ravindran Kannan</span>

Ravindran Kannan is a Principal Researcher at Microsoft Research India, where he leads the algorithms research group. He is also the first adjunct faculty of Computer Science and Automation Department of Indian Institute of Science.

<span class="mw-page-title-main">Margaret H. Wright</span> American computer scientist and applied mathematician (b. 1944)

Margaret H. Wright is an American computer scientist and mathematician. She is a Silver Professor of Computer Science and former Chair of the Computer Science department at Courant Institute of Mathematical Sciences, New York University, with research interests in optimization, linear algebra, and scientific computing. She was elected to the National Academy of Engineering in 1997 for development of numerical optimization algorithms and for leadership in the applied mathematics community. She was elected to the National Academy of Sciences in 2005. She was the first woman to serve as President of the Society for Industrial and Applied Mathematics.

Robert J. Vanderbei is an American mathematician and Professor in the Department of Operations Research and Financial Engineering at Princeton University.

<span class="mw-page-title-main">Criss-cross algorithm</span> Method for mathematical optimization

In mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear objective functions; there are criss-cross algorithms for linear-fractional programming problems, quadratic-programming problems, and linear complementarity problems.

<span class="mw-page-title-main">Klee–Minty cube</span> Unit hypercube of variable dimension whose corners have been perturbed

The Klee–Minty cube or Klee–Minty polytope is a unit hypercube of variable dimension whose corners have been perturbed. Klee and Minty demonstrated that George Dantzig's simplex algorithm has poor worst-case performance when initialized at one corner of their "squashed cube". On the three-dimensional version, the simplex algorithm and the criss-cross algorithm visit all 8 corners in the worst case.

<span class="mw-page-title-main">Alan Edelman</span> American mathematician

Alan Stuart Edelman is an American mathematician and computer scientist. He is a professor of applied mathematics at the Massachusetts Institute of Technology (MIT) and a Principal Investigator at the MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) where he leads a group in applied computing. In 2004, he founded a business called Interactive Supercomputing which was later acquired by Microsoft. Edelman is a fellow of American Mathematical Society (AMS), Society for Industrial and Applied Mathematics (SIAM), Institute of Electrical and Electronics Engineers (IEEE), and Association for Computing Machinery (ACM), for his contributions in numerical linear algebra, computational science, parallel computing, and random matrix theory. He is one of the cocreators of the technical programming language Julia.

<span class="mw-page-title-main">Affine scaling</span> Algorithm for solving linear programming problems

In mathematical optimization, affine scaling is an algorithm for solving linear programming problems. Specifically, it is an interior point method, discovered by Soviet mathematician I. I. Dikin in 1967 and reinvented in the U.S. in the mid-1980s.

<span class="mw-page-title-main">Inderjit Dhillon</span>

Inderjit S. Dhillon is the Gottesman Family Centennial Professor of Computer Science and Mathematics at the University of Texas at Austin, where he is also the Director of the ICES Center for Big Data Analytics. His main research interests are in machine learning, data analysis, parallel computing, network analysis, linear algebra and optimization.

<span class="mw-page-title-main">Tamás Terlaky</span> Hungarian mathematician (born 1955)

Tamás Terlaky is a Hungarian-Canadian-American professor of Industrial and Systems Engineering at Lehigh University. He is especially well known for his work on criss-cross algorithms, interior-point methods, Klee-Minty examples for path following algorithms, and optimization.

James Milton Renegar Jr. is an American mathematician, specializing in optimization algorithms for linear programming and nonlinear programming.

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 (1991). "A new parallel architecture for sparse matrix computation based on finite projective geometries". Proceedings of the 1991 ACM/IEEE conference on Supercomputing – Supercomputing '91. pp. 358–369. doi:10.1145/125826.126029. ISBN   0897914597. S2CID   6665759.
  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. ↑ 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, p. 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, p. 136148 (1994).
  9. ↑ Angier, Natalie (3 December 1984). "Folding the Perfect Corner". Time Magazine. Archived from the original on 4 December 2008. 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 [ bare URL ].
  15. ↑ Karmarkar, Narendra. "Advanced Algorithmic Approach to Optimization". Research in India. Retrieved 26 September 2003.
  16. ↑ "Focm 2014".
  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 page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.