Narendra Karmarkar

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 prix Fulkerson.

Biographie[modifier | modifier le code]

Nerendra Karmarkar a obtenu son PhD en 1983 à l'université de Californie à Berkeley, sous la direction de Richard Karp. Celui-ci portait sur les méthodes permettant de résoudre des problèmes NP-complets[1].

Travaux[modifier | modifier le code]

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

Distinctions[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

  1. (en) Narendra Karmarkar sur le site du Mathematics Genealogy Project
  2. Narendra Karmarkar, « A new polynomial-time algorithm for linear programming », Combinatorica, vol. 4,‎ 1984, p. 373–395.
  3. Lauréats du prix Fulkerson sur la page de la Mathematical Optimization Society.
  4. Page officielle du prix Kanellakis, pour l'année 2000.