Narendra Karmarkar

Narendra Karmarkar, né en 1957 à Gwalior dans le Madhya Pradesh, est un mathématicien indien, connu pour l'algorithme de Karmarkar, qui fut le premier algorithme polynomial vraiment efficace pour les problèmes d'optimisation linéaire. Cette méthode de points intérieurs est une découverte majeure pour laquelle il a notamment obtenu le prix Fulkerson.

Narendra Karmarkar

Biographie

Naissance	1957 Gwâlior
Nationalité	indienne
Formation	California Institute of Technology Université de Californie à Berkeley Institut indien de technologie de Bombay
Activités	Mathématicien, informaticien

Autres informations

A travaillé pour	Laboratoires Bell
Directeur de thèse	Richard Karp
Distinctions	Prix Frederick W. Lanchester (1984) Prix Fulkerson (1988) Prix Paris-Kanellakis (2000)

modifier - modifier le code - modifier Wikidata

Biographie

Nerendra Karmarkar a soutenu sa thèse de doctorat en 1983 à l'université de Californie à Berkeley, sous la direction de Richard Karp. Celle-ci portait sur les méthodes permettant de résoudre des problèmes NP-complets^[1]. Il a découvert un algorithme à coût polynomial pour la résolution des programmes linéaires (dite « méthode de point intérieur »), publié en 1984 alors qu'il était employé par les laboratoires Bell dans le New Jersey. Karmarkar a enseigné à l'Institut Tata de recherche fondamentale de Bombay.

Travaux

Karmarkar est surtout connu pour son algorithme polynomial pour l'optimisation linéaire publié en 1984^[2], et pour son implémentation efficace.

Distinctions

Karmarkar a reçu le prix Fulkerson en 1988^[3] et le prix Paris-Kanellakis en 2000^[4] pour son algorithme.