Narendra Karmarkar

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

Ausbildung und Karriere

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.

Heute ist Karmarkar als Professor am Tata Institute of Fundamental Research in Mumbai tätig.

Forschung

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 polynomielle Laufzeit besaß als auch praktisch einsetzbar war. Damit hob es sich von der 1979 von Leonid Chatschijan veröffentlichten Ellipsoidmethode ab, die zwar polynomiell, 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.

Preise und Ehrungen

• 1984: Frederick-W.-Lanchester-Preis
• 1988: Fulkerson-Preis der Mathematical Programming Society
• 2000: Paris-Kanellakis-Preis der Association for Computing Machinery

Weblinks

• Biographie (engl.) (Memento vom 11. April 2008 im Internet Archive) IIT Bombay Heritage Fund.