Editing Linear programming (section)

==== Projective algorithm of Karmarkar ====
{{main|Karmarkar's algorithm}}
Khachiyan's algorithm was of landmark importance for establishing the polynomial-time solvability of linear programs.  The algorithm was not a computational break-through, as the simplex method is more efficient for all but specially constructed families of linear programs.

However, Khachiyan's algorithm inspired new lines of research in linear programming. In 1984, [[Narendra Karmarkar|N. Karmarkar]] proposed a<!-- n interior-point --> [[projective method]] for linear programming.  Karmarkar's algorithm<ref name = "karmarkar84" /> improved on Khachiyan's<ref name = "khachiyan79" /> worst-case polynomial bound (giving <math>O(n^{3.5}L)</math>). Karmarkar claimed that his algorithm was much faster in practical LP than the simplex method, a claim that created great interest in interior-point methods.<ref name="Strang">{{cite journal|last=Strang|first=Gilbert|author-link=Gilbert Strang|title=Karmarkar's algorithm and its place in applied mathematics|journal=[[The Mathematical Intelligencer]]|date=1 June 1987|issn=0343-6993|pages=4–10|volume=9|doi=10.1007/BF03025891|mr=883185|issue=2|s2cid=123541868}}</ref> Since Karmarkar's discovery, many interior-point methods have been proposed and analyzed.