En 1984, Karmarkar a publié un algorithme de type point intérieur pour la programmation linéaire. Il a affirmé qu'en plus d'être de complexité polynomiale, il est plus efficace que le simplexe surtout pour des problèmes ...