Leonid Khachiyan
A new mathematical route to optimal solutions
Leonid Khachiyan was a mathematician and computer scientist of Armenian heritage, born in 1952. His work concerned optimisation, computational complexity and linear programming.
In 1979, he proved that linear programming problems could be solved in polynomial time using the ellipsoid method. This was a fundamental result in theoretical computer science, establishing a new understanding of the computational complexity of these problems.
Khachiyan received the Fulkerson Prize in 1982. He joined Rutgers University in 1990 and continued research and teaching there until his death in 2005. His name is associated with a major turning point in the history of optimisation algorithms.