Karmarkar's Algorithm

Karmarkar's algorithm, introduced by Narendra Karmarkar in 1984, solves linear programming problems and was the first reasonably efficient algorithm shown to solve them in polynomial time. It works from the interior of the feasible region rather than moving along its boundary as the earlier simplex method does. The previously known ellipsoid method was also polynomial time, but proved impractical, and Karmarkar's algorithm's practical efficiency helped launch the broader family of interior point methods.