Narendra Krishna Karmarkar (born 1956) is an Indian mathematician. He developed

Karmarkar's algorithm 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 pol ...

. He is listed as an

ISI highly cited researcher The Institute for Scientific Information (ISI) was an academic publishing service, founded by Eugene Garfield in Philadelphia in 1956. ISI offered scientometric and bibliographic database services. Its specialty was citation indexing and analysis ...

. He invented one of the first probably

polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

algorithms for

linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...

, 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 Nokia Bell Labs, commonly referred to as ''Bell Labs'', is an American industrial research and development company owned by Finnish technology company Nokia. With headquarters located in Murray Hill, New Jersey, the company operates several lab ...

New Jersey New Jersey is a U.S. state, state located in both the Mid-Atlantic States, Mid-Atlantic and Northeastern United States, Northeastern regions of the United States. Located at the geographic hub of the urban area, heavily urbanized Northeas ...

Biography

Karmarkar received his B.Tech. in electrical engineering from

IIT Bombay The Indian Institute of Technology Bombay (IIT- Bombay or IIT-B) is a Public university, public research university and Institute of technology, technical institute in Powai, Mumbai, Maharashtra, India. IIT Bombay is mainly known for the hig ...

in 1978,

M.S. A Master of Science (; abbreviated MS, M.S., MSc, M.Sc., SM, S.M., ScM or Sc.M.) is a master's degree. In contrast to the Master of Arts degree, the Master of Science degree is typically granted for studies in sciences, engineering and medicine ...

from the

California Institute of Technology The California Institute of Technology (branded as Caltech) is a private research university in Pasadena, California, United States. The university is responsible for many modern scientific advancements and is among a small group of institutes ...

in 1979, and

Ph.D. A Doctor of Philosophy (PhD, DPhil; or ) is a terminal degree that usually denotes the highest level of academic achievement in a given discipline and is awarded following a course of graduate study and original research. The name of the deg ...

in Computer Science from the

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California), is a Public university, public Land-grant university, land-grant research university in Berkeley, California, United States. Founded in 1868 and named after t ...

in 1983 under the supervision of

Richard M. Karp Richard Manning Karp (born January 3, 1935) is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing ...

. 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 Tata Institute of Fundamental Research (TIFR) is a leading research Institute under the Department of Atomic Energy of the Government of India. It is a public deemed university located at Navy Nagar, Colaba in Mumbai. It also has a centres in ...

Mumbai Mumbai ( ; ), also known as Bombay ( ; its official name until 1995), is the capital city of the Indian state of Maharashtra. Mumbai is the financial capital and the most populous city proper of India with an estimated population of 12 ...

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

problems in

. 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 method Interior-point methods (also referred to as barrier methods or IPMs) are algorithms for solving linear and non-linear convex optimization problems. IPMs combine two advantages of previously-known algorithms: * Theoretically, their run-time is po ...

s, some of which are used in current implementations of linear-program solvers.

Galois geometry

After working on the

, Karmarkar worked on a new

architecture Architecture is the art and technique of designing and building, as distinguished from the skills associated with construction. It is both the process and the product of sketching, conceiving, planning, designing, and construction, constructi ...

for

supercomputing A supercomputer is a type of computer with a high level of performance as compared to a general-purpose computer. The performance of a supercomputer is commonly measured in floating-point operations per second (FLOPS) instead of million instruc ...

, based on concepts from

finite geometry A finite geometry is any geometry, geometric system that has only a finite set, finite number of point (geometry), points. The familiar Euclidean geometry is not finite, because a Euclidean line contains infinitely many points. A geometry based ...

, especially

projective geometry In mathematics, projective geometry is the study of geometric properties that are invariant with respect to projective transformations. This means that, compared to elementary Euclidean geometry, projective geometry has a different setting (''p ...

over

finite fields In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subt ...

Awards

* The

Association for Computing Machinery The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional membe ...

awarded him the prestigious

Paris Kanellakis Award The Paris Kanellakis Theory and Practice Award is granted yearly by the Association for Computing Machinery (ACM) to honor "specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing". It wa ...

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

in Discrete Mathematics given jointly by the

American Mathematical Society The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...

Mathematical Programming Society The Mathematical Optimization Society (MOS), known as the Mathematical Programming Society (MPS) until 2010,American Academy of Achievement The American Academy of Achievement, colloquially known as the Academy of Achievement, is a nonprofit educational organization that recognizes some of the highest-achieving people in diverse fields and gives them the opportunity to meet one ano ...

, presented by former U.S. president (1985).
Frederick W. Lanchester Prize
of the

Operations Research Society of America The Institute for Operations Research and the Management Sciences (INFORMS) is an international society for practitioners in the fields of operations research (O.R.), management science, and analytics. It was established in 1995 with the merger of ...

for the Best Published Contributions to Operations Research (1984). * President of India gold medal, I.I.T. Bombay (1978).

References

External links

Distinguished Alumnus 1996
IIT Bombay

IIT Bombay Heritage Fund

in

Scilab Scilab is a free and open-source, cross-platform numerical computational package and a high-level, numerically oriented programming language. It can be used for signal processing, statistical analysis, image enhancement, fluid dynamics simul ...

{{DEFAULTSORT:Karmarkar, Narendra 1957 births Living people Indian theoretical computer scientists Numerical analysts 20th-century Indian mathematicians 21st-century Indian mathematicians American computer scientists Scientists at Bell Labs University of California, Berkeley alumni IIT Bombay alumni California Institute of Technology alumni Indian emigrants to the United States American operations researchers Indian operations researchers American academics of Indian descent People from Gwalior American people of Marathi descent Marathi people