Leonid Genrikhovich Khachiyan was a Soviet and American mathematician and computer scientist, born in Leningrad in 1952. In 1979 he devised the ellipsoid algorithm for linear programming, the first algorithm shown to solve linear programs in polynomial time, work for which he received the Fulkerson Prize in 1982. After earning his doctorate at the Computer Center of the Soviet Academy of Sciences, he later became a professor of computer science at Rutgers University, where he remained until his death in 2005.
Facts
FAQs
Why did Khachiyan's ellipsoid algorithm matter when the simplex method already worked well?
It was the first polynomial-time algorithm for linear programming and the first worst-case proof of efficiency.
The simplex method solved linear programming problems well in practice, but nobody had a formal proof that any method was efficient in the worst case. In 1979 Khachiyan's ellipsoid algorithm supplied that proof, as the first polynomial-time algorithm for linear programming. The same idea also applies to more general convex programming questions and can be used to approximate semidefinite programming. The result was recognized with the Fulkerson Prize in 1982.
Connections
In Field
Source Leonid Khachiyan (Wikipedia)
In the Other Atlases
Nationality
Also in Geography Atlas: the nationality of this subject.
Also in Geography Atlas: the nationality of this subject.
Sources
1. Wikidata: Leonid Khachiyan
- Wikidata Q1392167, resolved via en.wikipedia pageprops (wave rule R-L)
- Wikidata Q1392167 P569 (date of birth)
View the SourceLeonid Khachiyan (Wikipedia)
In Field: Algorithms and Complexity Theory, LeadQuote, In Field: Algorithms and Complexity Theory, Lead
He was most famous for his ellipsoid algorithm (1979) for linear programming, which was the first such algorithm known to have a polynomial running time.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.