Narendra Karmarkar

Narendra B. Karmarkar (* 1957) ist ein indischer Mathematiker. Sein wichtigster Beitrag war die Entwicklung eines polynomialen Algorithmus zur Lösung linearer Programme im Jahre 1984.

Karmarkar bekam 1978 seinen Bachelor am Indian Institute of Technology in Mumbai. Später erwarb er den Master of Science am California Institute of Technology und 1983 den Doktorgrad am Institut für Informatik der University of California, Berkeley.

Im Jahre 1984 veröffentlichte Karmarkar seinen Algorithmus, als er bei den Bell Laboratories in New Jersey arbeitete. Die Bedeutung dieses Innere-Punkte-Verfahrens lag darin, dass es das erste Lösungsverfahren zur Lösung linearer Programme war, das sowohl polynomiale Laufzeit besaß als auch praktisch einsetzbar war. Damit hob es sich von der 1979 von Leonid Chatschijan veröffentlichten Ellipsoidmethode ab, die zwar polynomial, aber für praktische Zwecke nicht geeignet war. Karmarkars Algorithmus förderte die Entwicklung weiterer Innere-Punkte-Verfahren wie Mehrotras Predictor-Corrector-Verfahren, von denen einige heute bei der Lösung bestimmter linearer Programme konkurrenzfähig zum Simplex-Verfahren sind.

Für seine Entdeckung erhielt Karmarkar zahlreiche Preise, unter anderem den Fulkerson-Preis der Mathematical Programming Society, den Paris-Kanellakis-Preis der Association for Computing Machinery, und den Frederick W. Lanchester Prize der Operations Research Society of America. Heute ist Karmarkar als Professor am Tata Institute of Fundamental Research in Mumbai tätig.

Weblinks

• Biographie (engl.) IIT Bombay Heritage Fund.