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 all hitherto existing society is the history of class struggles.”
—Karl Marx (1818–1883)
“Every generation rewrites the past. In easy times history is more or less of an ornamental art, but in times of danger we are driven to the written record by a pressing need to find answers to the riddles of today.... In times of change and danger when there is a quicksand of fear under men’s reasoning, a sense of continuity with generations gone before can stretch like a lifeline across the scary present and get us past that idiot delusion of the exceptional Now that blocks good thinking.”
—John Dos Passos (1896–1970)