History
The ellipsoid method has a long history. As an iterative method, a preliminary version was introduced by Naum Z. Shor. In 1972, an approximation algorithm for real convex minimization was studied by Arkadi Nemirovski and David B. Yudin (Judin). As an algorithm for solving linear programming problems with rational data, the ellipsoid algorithm was studied by Leonid Khachiyan: Khachiyan's achievement was to prove the polynomial-time solvability of linear programs.
Following Khachiyan's work, the ellipsoid method was the only algorithm for solving linear programs whose runtime had been proved to be polynomial until Karmarkar's algorithm. However, the interior-point method and variants of the simplex algorithm are much faster than the ellipsoid method in practice. Karmarkar's algorithm is also faster in the worst case.
However, the ellipsoidal algorithm allows complexity theorists to achieve (worst-case) bounds that depend on the dimension of the problem and on the size of the data, but not on the number of rows, so it remained important in combinatorial optimization theory for many decades. Only in the 21st Century have interior-point algorithms with similar complexity properties appeared.
Read more about this topic: Ellipsoid Method
Famous quotes containing the word history:
“The history of persecution is a history of endeavors to cheat nature, to make water run up hill, to twist a rope of sand.”
—Ralph Waldo Emerson (1803–1882)
“You that would judge me do not judge alone
This book or that, come to this hallowed place
Where my friends’ portraits hang and look thereon;
Ireland’s history in their lineaments trace;
Think where man’s glory most begins and ends
And say my glory was I had such friends.”
—William Butler Yeats (1865–1939)
“Revolutions are the periods of history when individuals count most.”
—Norman Mailer (b. 1923)